OpenRaiser/Intern-Atlas huggingface dataset:
The tractability of CSP classes defined by forbidden patterns
Venue: arXiv cs.AI 2014
Year: 2014

The constraint satisfaction problem (CSP) is a general problem central to computer science and artificial intelligence. Although the CSP is NP-hard in general, considerable effort has been spent on identifying tractable subclasses. The main two approaches consider structural properties (restrictions on the hypergraph of constraint scopes) and relational properties (restrictions on the language of constraint relations). Recently, some authors have considered hybrid properties that restrict the constraint hypergraph and the relations simultaneously. Our key contribution is the novel concept of a CSP pattern and classes of problems defined by forbidden patterns (which can be viewed as forbidding generic subproblems). We describe the theoretical framework which can be used to reason about classes of problems defined by forbidden patterns. We show that this framework generalises relational properties and allows us to capture known hybrid tractable classes. Although we are not close to obtaining a dichotomy concerning the tractability of general forbidden patterns, we are able to make some progress in a special case: classes of problems that arise when we can only forbid binary negative patterns (generic subproblems in which only inconsistent tuples are specified). In this case we are able to characterise very large classes of tractable and NP-hard forbidden patterns. This leaves the complexity of just one case unresolved and we conjecture that this last case is tractable.
Markov Decision Processes with Multiple Long-run Average Objectives
Venue: arXiv cs.GT 2014
Year: 2014

We study Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) functions. We consider two different objectives, namely, expectation and satisfaction objectives. Given an MDP with k limit-average functions, in the expectation objective the goal is to maximize the expected limit-average value, and in the satisfaction objective the goal is to maximize the probability of runs such that the limit-average value stays above a given vector. We show that under the expectation objective, in contrast to the case of one limit-average function, both randomization and memory are necessary for strategies even for epsilon-approximation, and that finite-memory randomized strategies are sufficient for achieving Pareto optimal values. Under the satisfaction objective, in contrast to the case of one limit-average function, infinite memory is necessary for strategies achieving a specific value (i.e. randomized finite-memory strategies are not sufficient), whereas memoryless randomized strategies are sufficient for epsilon-approximation, for all epsilon>0. We further prove that the decision problems for both expectation and satisfaction objectives can be solved in polynomial time and the trade-off curve (Pareto curve) can be epsilon-approximated in time polynomial in the size of the MDP and 1/epsilon, and exponential in the number of limit-average functions, for all epsilon>0. Our analysis also reveals flaws in previous work for MDPs with multiple mean-payoff functions under the expectation objective, corrects the flaws, and allows us to obtain improved results.
Curved Gabor Filters for Fingerprint Image Enhancement
Venue: arXiv cs.CV 2014
Year: 2014

Gabor filters play an important role in many application areas for the enhancement of various types of images and the extraction of Gabor features. For the purpose of enhancing curved structures in noisy images, we introduce curved Gabor filters which locally adapt their shape to the direction of flow. These curved Gabor filters enable the choice of filter parameters which increase the smoothing power without creating artifacts in the enhanced image. In this paper, curved Gabor filters are applied to the curved ridge and valley structure of low-quality fingerprint images. First, we combine two orientation field estimation methods in order to obtain a more robust estimation for very noisy images. Next, curved regions are constructed by following the respective local orientation and they are used for estimating the local ridge frequency. Lastly, curved Gabor filters are defined based on curved regions and they are applied for the enhancement of low-quality fingerprint images. Experimental results on the FVC2004 databases show improvements of this approach in comparison to state-of-the-art enhancement methods.
Stochastic Semantics and Statistical Model Checking for Networks of Priced Timed Automata
Venue: arXiv cs.SE 2014
Year: 2014

This paper offers a natural stochastic semantics of Networks of Priced Timed Automata (NPTA) based on races between components. The semantics provides the basis for satisfaction of probabilistic Weighted CTL properties (PWCTL), conservatively extending the classical satisfaction of timed automata with respect to TCTL. In particular the extension allows for hard real-time properties of timed automata expressible in TCTL to be refined by performance properties, e.g. in terms of probabilistic guarantees of time- and cost-bounded properties. A second contribution of the paper is the application of Statistical Model Checking (SMC) to efficiently estimate the correctness of non-nested PWCTL model checking problems with a desired level of confidence, based on a number of independent runs of the NPTA. In addition to applying classical SMC algorithms, we also offer an extension that allows to efficiently compare performance properties of NPTAs in a parametric setting. The third contribution is an efficient tool implementation of our result and applications to several case studies.
Network Congestion Control with Markovian Multipath Routing
Venue: arXiv cs.NI 2014
Year: 2014

In this paper we consider an integrated model for TCP/IP protocols with multipath routing. The model combines a Network Utility Maximization for rate control based on end-to-end queuing delays, with a Markovian Traffic Equilibrium for routing based on total expected delays. We prove the existence of a unique equilibrium state which is characterized as the solution of an unconstrained strictly convex program. A distributed algorithm for solving this optimization problem is proposed, with a brief discussion of how it can be implemented by adapting the current Internet protocols.
Serialising the ISO SynAF Syntactic Object Model
Venue: arXiv cs.CL 2014
Year: 2014

This paper introduces, an XML format developed to serialise the object model defined by the ISO Syntactic Annotation Framework SynAF. Based on widespread best practices we adapt a popular XML format for syntactic annotation, TigerXML, with additional features to support a variety of syntactic phenomena including constituent and dependency structures, binding, and different node types such as compounds or empty elements. We also define interfaces to other formats and standards including the Morpho-syntactic Annotation Framework MAF and the ISOCat Data Category Registry. Finally a case study of the German Treebank TueBa-D/Z is presented, showcasing the handling of constituent structures, topological fields and coreference annotation in tandem.
Robust Transceiver with Tomlinson-Harashima Precoding for Amplify-and-Forward MIMO Relaying Systems
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, robust transceiver design with Tomlinson-Harashima precoding (THP) for multi-hop amplify-and-forward (AF) multiple-input multiple-output (MIMO) relaying systems is investigated. At source node, THP is adopted to mitigate the spatial intersymbol interference. However, due to its nonlinear nature, THP is very sensitive to channel estimation errors. In order to reduce the effects of channel estimation errors, a joint Bayesian robust design of THP at source, linear forwarding matrices at relays and linear equalizer at destination is proposed. With novel applications of elegant characteristics of multiplicative convexity and matrix-monotone functions, the optimal structure of the nonlinear transceiver is first derived. Based on the derived structure, the transceiver design problem reduces to a much simpler one with only scalar variables which can be efficiently solved. Finally, the performance advantage of the proposed robust design over non-robust design is demonstrated by simulation results.
Generalized Post Embedding Problems
Venue: arXiv cs.LO 2014
Year: 2014

The Regular Post Embedding Problem extended with partial (co)directness is shown decidable. This extends to universal and/or counting versions. It is also shown that combining directness and codirectness in Post Embedding problems leads to undecidability.
Automatic sets of rational numbers
Venue: arXiv cs.FL 2014
Year: 2014

The notion of a k-automatic set of integers is well-studied. We develop a new notion - the k-automatic set of rational numbers - and prove basic properties of these sets, including closure properties and decidability.
Improved Upper Bounds for Pairing Heaps
Venue: arXiv cs.DS 2014
Year: 2014

Pairing heaps are shown to have constant amortized time Insert and Meld, thus showing that pairing heaps have the same amortized runtimes as Fibonacci heaps for all operations but Decrease-key.
Generalized Orthogonal Matching Pursuit
Venue: arXiv cs.IT 2014
Year: 2014

As a greedy algorithm to recover sparse signals from compressed measurements, orthogonal matching pursuit (OMP) algorithm has received much attention in recent years. In this paper, we introduce an extension of the OMP for pursuing efficiency in reconstructing sparse signals. Our approach, henceforth referred to as generalized OMP (gOMP), is literally a generalization of the OMP in the sense that multiple $N$ indices are identified per iteration. Owing to the selection of multiple ''correct'' indices, the gOMP algorithm is finished with much smaller number of iterations when compared to the OMP. We show that the gOMP can perfectly reconstruct any $K$-sparse signals ($K > 1$), provided that the sensing matrix satisfies the RIP with $δ_{NK} < \frac{\sqrt{N}}{\sqrt{K} + 3 \sqrt{N}}$. We also demonstrate by empirical simulations that the gOMP has excellent recovery performance comparable to $\ell_1$-minimization technique with fast processing speed and competitive computational complexity.
A Nonstochastic Information Theory for Communication and State Estimation
Venue: arXiv cs.SY 2014
Year: 2014

In communications, unknown variables are usually modelled as random variables, and concepts such as independence, entropy and information are defined in terms of the underlying probability distributions. In contrast, control theory often treats uncertainties and disturbances as bounded unknowns having no statistical structure. The area of networked control combines both fields, raising the question of whether it is possible to construct meaningful analogues of stochastic concepts such as independence, Markovness, entropy and information without assuming a probability space. This paper introduces a framework for doing so, leading to the construction of a maximin information functional for nonstochastic variables. It is shown that the largest maximin information rate through a memoryless, error-prone channel in this framework coincides with the block-coding zero-error capacity of the channel. Maximin information is then used to derive tight conditions for uniformly estimating the state of a linear time-invariant system over such a channel, paralleling recent results of Matveev and Savkin.
Informatics Perspectives on Decision Taking, a Case Study on Resolving Process Product Ambiguity
Venue: arXiv cs.OH 2014
Year: 2014

A decision is an act or event of decision taking. Decision making always includes decision taking, the latter not involving significant exchanges with non-deciding agents. A decision outcome is a piece of storable information constituting the result of a decision. Decision outcomes are typed, for instance: plan, command, assertion, or boolean reply to a question. Decision outcomes are seen by an audience and autonomous actions from the audience is supposed to realize the putting into effect of a decision outcome, thus leading to so-called decision effects. Decision outcomes are supposedly expected by the decider. Using a model or a theory concerning the causal chain leading from a decision outcome to one or more decision effects may support a decision taker decision taker in predicting plausible decision effects for candidate decision outcomes. Decision taking is positioned amidst many related notions including: decision making, decision process, decision making process, decision process making, decision engineering, decision progression, and decision progression production.
Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies
Venue: arXiv cs.DM 2014
Year: 2014

We consider the problem of balancing load items (tokens) in networks. Starting with an arbitrary load distribution, we allow nodes to exchange tokens with their neighbors in each round. The goal is to achieve a distribution where all nodes have nearly the same number of tokens. For the continuous case where tokens are arbitrarily divisible, most load balancing schemes correspond to Markov chains, whose convergence is fairly well-understood in terms of their spectral gap. However, in many applications, load items cannot be divided arbitrarily, and we need to deal with the discrete case where the load is composed of indivisible tokens. This discretization entails a non-linear behavior due to its rounding errors, which makes this analysis much harder than in the continuous case. We investigate several randomized protocols for different communication models in the discrete case. As our main result, we prove that for any regular network in the matching model, all nodes have the same load up to an additive constant in (asymptotically) the same number of rounds as required in the continuous case. This generalizes and tightens the previous best result, which only holds for expander graphs, and demonstrates that there is almost no difference between the discrete and continuous cases. Our results also provide a positive answer to the question of how well discrete load balancing can be approximated by (continuous) Markov chains, which has been posed by many researchers.
Parameterized and Approximation Algorithms for Boxicity
Venue: arXiv cs.DS 2014
Year: 2014

Boxicity of a graph $G(V,$ $E)$, denoted by $box(G)$, is the minimum integer $k$ such that $G$ can be represented as the intersection graph of axis parallel boxes in $\mathbb{R}^k$. The problem of computing boxicity is inapproximable even for graph classes like bipartite, co-bipartite and split graphs within $O(n^{1 - ε})$-factor, for any $ε>0$ in polynomial time unless $NP=ZPP$. We give FPT approximation algorithms for computing the boxicity of graphs, where the parameter used is the vertex or edge edit distance of the given graph from families of graphs of bounded boxicity. This can be seen as a generalization of the parameterizations discussed in \cite{Adiga2}. Extending the same idea in one of our algorithms, we also get an $O\left(\frac{n\sqrt{\log \log n}}{\sqrt{\log n}}\right)$ factor approximation algorithm for computing boxicity and an $O\left(\frac{n {(\log \log n)}^{\frac{3}{2}}}{\sqrt{\log n}}\right)$ factor approximation algorithm for computing the cubicity. These seem to be the first $o(n)$ factor approximation algorithms known for both boxicity and cubicity. As a consequence of this result, a $o(n)$ factor approximation algorithm for computing the partial order dimension of finite posets and a $o(n)$ factor approximation algorithm for computing the threshold dimension of split graphs would follow.
A Polynomial Time Approximation Scheme for a Single Machine Scheduling Problem Using a Hybrid Evolutionary Algorithm
Venue: arXiv cs.NE 2014
Year: 2014

Nowadays hybrid evolutionary algorithms, i.e, heuristic search algorithms combining several mutation operators some of which are meant to implement stochastically a well known technique designed for the specific problem in question while some others playing the role of random search, have become rather popular for tackling various NP-hard optimization problems. While empirical studies demonstrate that hybrid evolutionary algorithms are frequently successful at finding solutions having fitness sufficiently close to the optimal, many fewer articles address the computational complexity in a mathematically rigorous fashion. This paper is devoted to a mathematically motivated design and analysis of a parameterized family of evolutionary algorithms which provides a polynomial time approximation scheme for one of the well-known NP-hard combinatorial optimization problems, namely the "single machine scheduling problem without precedence constraints". The authors hope that the techniques and ideas developed in this article may be applied in many other situations.
Truthful Mechanisms for Competing Submodular Processes
Venue: arXiv cs.GT 2014
Year: 2014

Motivated by applications to word-of-mouth advertising, we consider a game-theoretic scenario in which competing advertisers want to target initial adopters in a social network. Each advertiser wishes to maximize the resulting cascade of influence, modeled by a general network diffusion process. However, competition between products may adversely impact the rate of adoption for any given firm. The resulting framework gives rise to complex preferences that depend on the specifics of the stochastic diffusion model and the network topology. We study this model from the perspective of a central mechanism, such as a social networking platform, that can optimize seed placement as a service for the advertisers. We ask: given the reported demands of the competing firms, how should a mechanism choose seeds to maximize overall efficiency? Beyond the algorithmic problem, competition raises issues of strategic behaviour: rational agents should not be incentivized to underreport their budget demands. We show that when there are two players, the social welfare can be $2$-approximated by a polynomial-time strategyproof mechanism. Our mechanism is defined recursively, randomizing the order in which advertisers are allocated seeds according to a particular greedy method. For three or more players, we demonstrate that under additional assumptions (satisfied by many existing models of influence spread) there exists a simpler strategyproof $\frac{e}{e-1}$-approximation mechanism; notably, this second mechanism is not necessarily strategyproof when there are only two players.
Late Weak Bisimulation for Markov Automata
Venue: arXiv cs.FL 2014
Year: 2014

Weak bisimilarity is a distribution-based equivalence notion for Markov automata. It has gained some popularity as the coarsest reasonable behavioural equivalence on Markov automata. This paper studies a strictly coarser notion: Late weak bisimilarity enjoys valuable properties if restricting to important subclasses of schedulers: Trace distribution equivalence is implied for partial information schedulers, and compositionality is preserved by distributed schedulers. The intersection of the two scheduler classes thus spans a coarser and still reasonable compositional theory of Markov automata.
Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems
Venue: arXiv cs.CC 2014
Year: 2014

Partitioning the vertices of a graph into two roughly equal parts while minimizing the number of edges crossing the cut is a fundamental problem (called Balanced Separator) that arises in many settings. For this problem, and variants such as the Uniform Sparsest Cut problem where the goal is to minimize the fraction of pairs on opposite sides of the cut that are connected by an edge, there are large gaps between the known approximation algorithms and non-approximability results. While no constant factor approximation algorithms are known, even APX-hardness is not known either. In this work we prove that for balanced separator and uniform sparsest cut, semidefinite programs from the Lasserre hierarchy (which are the most powerful relaxations studied in the literature) have an integrality gap bounded away from $1$, even for $Ω(n)$ levels of the hierarchy. This complements recent algorithmic results in Guruswami and Sinop (2011) which used the Lasserre hierarchy to give an approximation scheme for these problems (with runtime depending on the spectrum of the graph). Along the way, we make an observation that simplifies the task of lifting "polynomial constraints" (such as the global balance constraint in balanced separator) to higher levels of the Lasserre hierarchy.
Control Theoretic Optimization of 802.11 WLANs: Implementation and Experimental Evaluation
Venue: arXiv cs.NI 2014
Year: 2014

In 802.11 WLANs, adapting the contention parameters to network conditions results in substantial performance improvements. Even though the ability to change these parameters has been available in standard devices for years, so far no adaptive mechanism using this functionality has been validated in a realistic deployment. In this paper we report our experiences with implementing and evaluating two adaptive algorithms based on control theory, one centralized and one distributed, in a large-scale testbed consisting of 18 commercial off-the-shelf devices. We conduct extensive measurements, considering different network conditions in terms of number of active nodes, link qualities and traffic generated. We show that both algorithms significantly outperform the standard configuration in terms of total throughput. We also identify the limitations inherent in distributed schemes, and demonstrate that the centralized approach substantially improves performance under a large variety of scenarios, which confirms its suitability for real deployments.
Calibrating Data to Sensitivity in Private Data Analysis
Venue: arXiv cs.CR 2014
Year: 2014

We present an approach to differentially private computation in which one does not scale up the magnitude of noise for challenging queries, but rather scales down the contributions of challenging records. While scaling down all records uniformly is equivalent to scaling up the noise magnitude, we show that scaling records non-uniformly can result in substantially higher accuracy by bypassing the worst-case requirements of differential privacy for the noise magnitudes. This paper details the data analysis platform wPINQ, which generalizes the Privacy Integrated Query (PINQ) to weighted datasets. Using a few simple operators (including a non-uniformly scaling Join operator) wPINQ can reproduce (and improve) several recent results on graph analysis and introduce new generalizations (e.g., counting triangles with given degrees). We also show how to integrate probabilistic inference techniques to synthesize datasets respecting more complicated (and less easily interpreted) measurements.
Picture-Hanging Puzzles
Venue: arXiv cs.DS 2014
Year: 2014

We show how to hang a picture by wrapping rope around n nails, making a polynomial number of twists, such that the picture falls whenever any k out of the n nails get removed, and the picture remains hanging when fewer than k nails get removed. This construction makes for some fun mathematical magic performances. More generally, we characterize the possible Boolean functions characterizing when the picture falls in terms of which nails get removed as all monotone Boolean functions. This construction requires an exponential number of twists in the worst case, but exponential complexity is almost always necessary for general functions.