OpenRaiser/Intern-Atlas huggingface dataset:
High Order Implicit-Explicit General Linear Methods with Optimized Stability Regions
Venue: arXiv cs.NA 2014
Year: 2014

In the numerical solution of partial differential equations using a method-of-lines approach, the availability of high order spatial discretization schemes motivates the development of sophisticated high order time integration methods. For multiphysics problems with both stiff and non-stiff terms implicit-explicit (IMEX) time stepping methods attempt to combine the lower cost advantage of explicit schemes with the favorable stability properties of implicit schemes. Existing high order IMEX Runge Kutta or linear multistep methods, however, suffer from accuracy or stability reduction. This work shows that IMEX general linear methods (GLMs) are competitive alternatives to classic IMEX schemes for large problems arising in practice. High order IMEX-GLMs are constructed in the framework developed by the authors [34]. The stability regions of the new schemes are optimized numerically. The resulting IMEX-GLMs have similar stability properties as IMEX Runge-Kutta methods, but they do not suffer from order reduction, and are superior in terms of accuracy and efficiency. Numerical experiments with two and three dimensional test problems illustrate the potential of the new schemes to speed up complex applications.
On the Erdos Discrepancy Problem
Venue: arXiv cs.DM 2014
Year: 2014

According to the Erdős discrepancy conjecture, for any infinite $\pm 1$ sequence, there exists a homogeneous arithmetic progression of unbounded discrepancy. In other words, for any $\pm 1$ sequence $(x_1,x_2,...)$ and a discrepancy $C$, there exist integers $m$ and $d$ such that $|\sum_{i=1}^m x_{i \cdot d}| > C$. This is an $80$-year-old open problem and recent development proved that this conjecture is true for discrepancies up to $2$. Paul Erdős also conjectured that this property of unbounded discrepancy even holds for the restricted case of completely multiplicative sequences (CMSs), namely sequences $(x_1,x_2,...)$ where $x_{a \cdot b} = x_{a} \cdot x_{b}$ for any $a,b \geq 1$. The longest CMS with discrepancy $2$ has been proven to be of size $246$. In this paper, we prove that any completely multiplicative sequence of size $127,646$ or more has discrepancy at least $4$, proving the Erdős discrepancy conjecture for CMSs of discrepancies up to $3$. In addition, we prove that this bound is tight and increases the size of the longest known sequence of discrepancy $3$ from $17,000$ to $127,645$. Finally, we provide inductive construction rules as well as streamlining methods to improve the lower bounds for sequences of higher discrepancies.
Learning Probabilistic Programs
Venue: arXiv cs.AI 2014
Year: 2014

We develop a technique for generalising from data in which models are samplers represented as program text. We establish encouraging empirical results that suggest that Markov chain Monte Carlo probabilistic programming inference techniques coupled with higher-order probabilistic programming languages are now sufficiently powerful to enable successful inference of this kind in nontrivial domains. We also introduce a new notion of probabilistic program compilation and show how the same machinery might be used in the future to compile probabilistic programs for efficient reusable predictive inference.
Quality Estimation Of Machine Translation Outputs Through Stemming
Venue: arXiv cs.CL 2014
Year: 2014

Machine Translation is the challenging problem for Indian languages. Every day we can see some machine translators being developed, but getting a high quality automatic translation is still a very distant dream . The correct translated sentence for Hindi language is rarely found. In this paper, we are emphasizing on English-Hindi language pair, so in order to preserve the correct MT output we present a ranking system, which employs some machine learning techniques and morphological features. In ranking no human intervention is required. We have also validated our results by comparing it with human ranking.
A Convex Formulation for Learning Scale-Free Networks via Submodular Relaxation
Venue: arXiv cs.LG 2014
Year: 2014

A key problem in statistics and machine learning is the determination of network structure from data. We consider the case where the structure of the graph to be reconstructed is known to be scale-free. We show that in such cases it is natural to formulate structured sparsity inducing priors using submodular functions, and we use their Lovász extension to obtain a convex relaxation. For tractable classes such as Gaussian graphical models, this leads to a convex optimization problem that can be efficiently solved. We show that our method results in an improvement in the accuracy of reconstructed networks for synthetic data. We also show how our prior encourages scale-free reconstructions on a bioinfomatics dataset.
ARTOS -- Adaptive Real-Time Object Detection System
Venue: arXiv cs.CV 2014
Year: 2014

ARTOS is all about creating, tuning, and applying object detection models with just a few clicks. In particular, ARTOS facilitates learning of models for visual object detection by eliminating the burden of having to collect and annotate a large set of positive and negative samples manually and in addition it implements a fast learning technique to reduce the time needed for the learning step. A clean and friendly GUI guides the user through the process of model creation, adaptation of learned models to different domains using in-situ images, and object detection on both offline images and images from a video stream. A library written in C++ provides the main functionality of ARTOS with a C-style procedural interface, so that it can be easily integrated with any other project.
A domain-specific analysis system for examining nuclear reactor simulation data for light-water and sodium-cooled fast reactors
Venue: arXiv cs.CE 2014
Year: 2014

Building a new generation of fission reactors in the United States presents many technical and regulatory challenges. One important challenge is the need to share and present results from new high-fidelity, high-performance simulations in an easily usable way. Since modern multiscale, multi-physics simulations can generate petabytes of data, they will require the development of new techniques and methods to reduce the data to familiar quantities of interest (e.g., pin powers, temperatures) with a more reasonable resolution and size. Furthermore, some of the results from these simulations may be new quantities for which visualization and analysis techniques are not immediately available in the community and need to be developed. This paper describes a new system for managing high-performance simulation results in a domain-specific way that naturally exposes quantities of interest for light water and sodium-cooled fast reactors. It describes requirements to build such a system and the technical challenges faced in its development at all levels (simulation, user interface, etc.). An example comparing results from two different simulation suites for a single assembly in a light-water reactor is presented, along with a detailed discussion of the system's requirements and design.
XML Matchers: approaches and challenges
Venue: arXiv cs.DB 2014
Year: 2014

Schema Matching, i.e. the process of discovering semantic correspondences between concepts adopted in different data source schemas, has been a key topic in Database and Artificial Intelligence research areas for many years. In the past, it was largely investigated especially for classical database models (e.g., E/R schemas, relational databases, etc.). However, in the latest years, the widespread adoption of XML in the most disparate application fields pushed a growing number of researchers to design XML-specific Schema Matching approaches, called XML Matchers, aiming at finding semantic matchings between concepts defined in DTDs and XSDs. XML Matchers do not just take well-known techniques originally designed for other data models and apply them on DTDs/XSDs, but they exploit specific XML features (e.g., the hierarchical structure of a DTD/XSD) to improve the performance of the Schema Matching process. The design of XML Matchers is currently a well-established research area. The main goal of this paper is to provide a detailed description and classification of XML Matchers. We first describe to what extent the specificities of DTDs/XSDs impact on the Schema Matching task. Then we introduce a template, called XML Matcher Template, that describes the main components of an XML Matcher, their role and behavior. We illustrate how each of these components has been implemented in some popular XML Matchers. We consider our XML Matcher Template as the baseline for objectively comparing approaches that, at first glance, might appear as unrelated. The introduction of this template can be useful in the design of future XML Matchers. Finally, we analyze commercial tools implementing XML Matchers and introduce two challenging issues strictly related to this topic, namely XML source clustering and uncertainty management in XML Matchers.
Real-Time Scheduling for Content Broadcasting in LTE
Venue: arXiv cs.NI 2014
Year: 2014

Broadcasting capabilities are one of the most promising features of upcoming LTE-Advanced networks. However, the task of scheduling broadcasting sessions is far from trivial, since it affects the available resources of several contiguous cells as well as the amount of resources that can be devoted to unicast traffic. In this paper, we present a compact, convenient model for broadcasting in LTE, as well as a set of efficient algorithms to define broadcasting areas and to actually perform content scheduling. We study the performance of our algorithms in a realistic scenario, deriving interesting insights on the possible trade-offs between effectiveness and computational efficiency.
Signature Limits: An Entire Map of Clone Features and their Discovery in Nearly Linear Time
Venue: arXiv cs.CR 2014
Year: 2014

We address the problem of creating entire and complete maps of software code clones (copy features in data) in a corpus of binary artifacts of unknown provenance. We report on a practical methodology, which employs enhanced suffix data structures and partial orderings of clones to compute a compact representation of most interesting clones features in data. The enumeration of clone features is useful for malware triage and prioritization when human exploration, testing and verification is the most costly factor. We further show that the enhanced arrays may be used for discovery of provenance relations in data and we introduce two distinct Jaccard similarity coefficients to measure code similarity in binary artifacts. We illustrate the use of these tools on real malware data including a retro-diction experiment for measuring and enumerating evidence supporting common provenance in {\it Stuxnet} and {\it Duqu}. The results indicate the practicality and efficacy of mapping completely the clone features in data.
Consensus in multi-agent systems with second-order dynamics and non-periodic sampled-data exchange
Venue: arXiv cs.SY 2014
Year: 2014

In this paper consensus in second-order multi-agent systems with a non-periodic sampled-data exchange among agents is investigated. The sampling is random with bounded inter-sampling intervals. It is assumed that each agent has exact knowledge of its own state at all times. The considered local interaction rule is PD-type. The characterization of the convergence properties exploits a Lyapunov-Krasovskii functional method, sufficient conditions for stability of the consensus protocol to a time-invariant value are derived. Numerical simulations are presented to corroborate the theoretical results.
2-Edge Connectivity in Directed Graphs
Venue: arXiv cs.DS 2014
Year: 2014

Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly not much has been investigated for directed graphs. In this paper we study $2$-edge connectivity problems in directed graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices $v$ and $w$ are $2$-edge-connected if there are two edge-disjoint paths from $v$ to $w$ and two edge-disjoint paths from $w$ to $v$. This relation partitions the vertices into blocks such that all vertices in the same block are $2$-edge-connected. Differently from the undirected case, those blocks do not correspond to the $2$-edge-connected components of the graph. We show how to compute this relation in linear time so that we can report in constant time if two vertices are $2$-edge-connected. We also show how to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has $O(n)$ edges and maintains the same $2$-edge-connected blocks as the input graph.
Charge Scheduling of an Energy Storage System under Time-of-use Pricing and a Demand Charge
Venue: arXiv cs.NE 2014
Year: 2014

A real-coded genetic algorithm is used to schedule the charging of an energy storage system (ESS), operated in tandem with renewable power by an electricity consumer who is subject to time-of-use pricing and a demand charge. Simulations based on load and generation profiles of typical residential customers show that an ESS scheduled by our algorithm can reduce electricity costs by approximately 17%, compared to a system without an ESS, and by 8% compared to a scheduling algorithm based on net power.
A tableau for set-satisfiability for extended fuzzy logic BL
Venue: arXiv cs.LO 2014
Year: 2014

This paper presents a tableau calculus for finding a model for a set-satisfiable finite set of formulas of an extended fuzzy logic BL, a fuzzy logic BL with additional Baaz connective and the involutive negation, if such a model exists. The calculus is a generalisation of a tableau calculus for BL, which is based on the decomposition theorem for a continuous t-norm. The aforementioned tableau calculus for BL is used to prove that a formula A of the extended BL is valid with respect to all continuous t-norms or to find a continuous t-norm * and assignment V of propositional atoms to [0,1] such that *-evaluation V*(A)<1. The tableau calculus presented in this paper enables for a finite set of formulas F of the extended BL and a subset K of [0,1] to find a continuous t-norm * and assignment V of propositional atoms to [0,1] such that *-evaluation V*(A) belongs to K for all formulas A that belong to F, or alternatively to show that such a model does not exist.
A Comparison of Blocking Methods for Record Linkage
Venue: arXiv cs.DB 2014
Year: 2014

Record linkage seeks to merge databases and to remove duplicates when unique identifiers are not available. Most approaches use blocking techniques to reduce the computational complexity associated with record linkage. We review traditional blocking techniques, which typically partition the records according to a set of field attributes, and consider two variants of a method known as locality sensitive hashing, sometimes referred to as "private blocking." We compare these approaches in terms of their recall, reduction ratio, and computational complexity. We evaluate these methods using different synthetic datafiles and conclude with a discussion of privacy-related issues.
Optimally Stabilized PET Image Denoising Using Trilateral Filtering
Venue: arXiv cs.CV 2014
Year: 2014

Low-resolution and signal-dependent noise distribution in positron emission tomography (PET) images makes denoising process an inevitable step prior to qualitative and quantitative image analysis tasks. Conventional PET denoising methods either over-smooth small-sized structures due to resolution limitation or make incorrect assumptions about the noise characteristics. Therefore, clinically important quantitative information may be corrupted. To address these challenges, we introduced a novel approach to remove signal-dependent noise in the PET images where the noise distribution was considered as Poisson-Gaussian mixed. Meanwhile, the generalized Anscombe's transformation (GAT) was used to stabilize varying nature of the PET noise. Other than noise stabilization, it is also desirable for the noise removal filter to preserve the boundaries of the structures while smoothing the noisy regions. Indeed, it is important to avoid significant loss of quantitative information such as standard uptake value (SUV)-based metrics as well as metabolic lesion volume. To satisfy all these properties, we extended bilateral filtering method into trilateral filtering through multiscaling and optimal Gaussianization process. The proposed method was tested on more than 50 PET-CT images from various patients having different cancers and achieved the superior performance compared to the widely used denoising techniques in the literature.
Symbolic Algorithms for Language Equivalence and Kleene Algebra with Tests
Venue: arXiv cs.FL 2014
Year: 2014

We first propose algorithms for checking language equivalence of finite automata over a large alphabet. We use symbolic automata, where the transition function is compactly represented using a (multi-terminal) binary decision diagrams (BDD). The key idea consists in computing a bisimulation by exploring reachable pairs symbolically, so as to avoid redundancies. This idea can be combined with already existing optimisations, and we show in particular a nice integration with the disjoint sets forest data-structure from Hopcroft and Karp's standard algorithm. Then we consider Kleene algebra with tests (KAT), an algebraic theory that can be used for verification in various domains ranging from compiler optimisation to network programming analysis. This theory is decidable by reduction to language equivalence of automata on guarded strings, a particular kind of automata that have exponentially large alphabets. We propose several methods allowing to construct symbolic automata out of KAT expressions, based either on Brzozowski's derivatives or standard automata constructions. All in all, this results in efficient algorithms for deciding equivalence of KAT expressions.
Computational Aspects of Multi-Winner Approval Voting
Venue: arXiv cs.GT 2014
Year: 2014

We study computational aspects of three prominent voting rules that use approval ballots to elect multiple winners. These rules are satisfaction approval voting, proportional approval voting, and reweighted approval voting. We first show that computing the winner for proportional approval voting is NP-hard, closing a long standing open problem. As none of the rules are strategyproof, even for dichotomous preferences, we study various strategic aspects of the rules. In particular, we examine the computational complexity of computing a best response for both a single agent and a group of agents. In many settings, we show that it is NP-hard for an agent or agents to compute how best to vote given a fixed set of approval ballots from the other agents.
Elements of Design for Containers and Solutions in the LinBox Library
Venue: arXiv cs.MS 2014
Year: 2014

We describe in this paper new design techniques used in the \cpp exact linear algebra library \linbox, intended to make the library safer and easier to use, while keeping it generic and efficient. First, we review the new simplified structure for containers, based on our \emph{founding scope allocation} model. We explain design choices and their impact on coding: unification of our matrix classes, clearer model for matrices and submatrices, \etc Then we present a variation of the \emph{strategy} design pattern that is comprised of a controller--plugin system: the controller (solution) chooses among plug-ins (algorithms) that always call back the controllers for subtasks. We give examples using the solution \mul. Finally we present a benchmark architecture that serves two purposes: Providing the user with easier ways to produce graphs; Creating a framework for automatically tuning the library and supporting regression testing.
Solvability-Based Comparison of Failure Detectors
Venue: arXiv cs.DC 2014
Year: 2014

Failure detectors are oracles that have been introduced to provide processes in asynchronous systems with information about faults. This information can then be used to solve problems otherwise unsolvable in asynchronous systems. A natural question is on the "minimum amount of information" a failure detector has to provide for a given problem. This question is classically addressed using a relation that states that a failure detector D is stronger (that is, provides "more, or better, information") than a failure detector D' if D can be used to implement D'. It has recently been shown that this classic implementability relation has some drawbacks. To overcome this, different relations have been defined, one of which states that a failure detector D is stronger than D' if D can solve all the time-free problems solvable by D'. In this paper we compare the implementability-based hierarchy of failure detectors to the hierarchy based on solvability. This is done by introducing a new proof technique for establishing the solvability relation. We apply this technique to known failure detectors from the literature and demonstrate significant differences between the hierarchies.
Faster polynomial multiplication over finite fields
Venue: arXiv cs.CC 2014
Year: 2014

Let p be a prime, and let M_p(n) denote the bit complexity of multiplying two polynomials in F_p[X] of degree less than n. For n large compared to p, we establish the bound M_p(n) = O(n log n 8^(log^* n) log p), where log^* is the iterated logarithm. This is the first known Fürer-type complexity bound for F_p[X], and improves on the previously best known bound M_p(n) = O(n log n log log n log p).
The Tractability Frontier of Graph-Like First-Order Query Sets
Venue: arXiv cs.LO 2014
Year: 2014

We study first-order model checking, by which we refer to the problem of deciding whether or not a given first-order sentence is satisfied by a given finite structure. In particular, we aim to understand on which sets of sentences this problem is tractable, in the sense of parameterized complexity theory. To this end, we define the notion of a graph-like sentence set, which definition is inspired by previous work on first-order model checking wherein the permitted connectives and quantifiers were restricted. Our main theorem is the complete tractability classification of such graph-like sentence sets, which is (to our knowledge) the first complexity classification theorem concerning a class of sentences that has no restriction on the connectives and quantifiers. To present and prove our classification, we introduce and develop a novel complexity-theoretic framework which is built on parameterized complexity and includes new notions of reduction.