OpenRaiser/Intern-Atlas huggingface dataset:
Tractable hypergraph properties for constraint satisfaction and conjunctive queries
Venue: arXiv cs.DS 2011
Year: 2011

An important question in the study of constraint satisfaction problems (CSP) is understanding how the graph or hypergraph describing the incidence structure of the constraints influences the complexity of the problem. For binary CSP instances (i.e., where each constraint involves only two variables), the situation is well understood: the complexity of the problem essentially depends on the treewidth of the graph of the constraints. However, this is not the correct answer if constraints with unbounded number of variables are allowed, and in particular, for CSP instances arising from query evaluation problems in database theory. Formally, if H is a class of hypergraphs, then let CSP(H) be CSP restricted to instances whose hypergraph is in H. Our goal is to characterize those classes of hypergraphs for which CSP(H) is polynomial-time solvable or fixed-parameter tractable, parameterized by the number of variables. Note that in the applications related to database query evaluation, we usually assume that the number of variables is much smaller than the size of the instance, thus parameterization by the number of variables is a meaningful question. The most general known property of H that makes CSP(H) polynomial-time solvable is bounded fractional hypertree width. Here we introduce a new hypergraph measure called submodular width, and show that bounded submodular width of H implies that CSP(H) is fixed-parameter tractable. In a matching hardness result, we show that if H has unbounded submodular width, then CSP(H) is not fixed-parameter tractable, unless the Exponential Time Hypothesis fails.
Distances on Rhombus Tilings
Venue: arXiv cs.DM 2011
Year: 2011

The rhombus tilings of a simply connected domain of the Euclidean plane are known to form a flip-connected space (a flip is the elementary operation on rhombus tilings which rotates 180° a hexagon made of three rhombi). Motivated by the study of a quasicrystal growth model, we are here interested in better understanding how "tight" rhombus tiling spaces are flip-connected. We introduce a lower bound (Hamming-distance) on the minimal number of flips to link two tilings (flip-distance), and we investigate whether it is sharp. The answer depends on the number n of different edge directions in the tiling: positive for n=3 (dimer tilings) or n=4 (octogonal tilings), but possibly negative for n=5 (decagonal tilings) or greater values of n. A standard proof is provided for the n=3 and n=4 cases, while the complexity of the n=5 case led to a computer-assisted proof (whose main result can however be easily checked by hand).
Coding Guidelines for Prolog
Venue: arXiv cs.PL 2011
Year: 2011

Coding standards and good practices are fundamental to a disciplined approach to software projects, whatever programming languages they employ. Prolog programming can benefit from such an approach, perhaps more than programming in other languages. Despite this, no widely accepted standards and practices seem to have emerged up to now. The present paper is a first step towards filling this void: it provides immediate guidelines for code layout, naming conventions, documentation, proper use of Prolog features, program development, debugging and testing. Presented with each guideline is its rationale and, where sensible options exist, illustrations of the relative pros and cons for each alternative. A coding standard should always be selected on a per-project basis, based on a host of issues pertinent to any given programming project; for this reason the paper goes beyond the mere provision of normative guidelines by discussing key factors and important criteria that should be taken into account when deciding on a fully-fledged coding standard for the project.
Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
Venue: arXiv cs.CG 2011
Year: 2011

Given a set $Σ$ of spheres in $\mathbb{E}^d$, with $d\ge{}3$ and $d$ odd, having a fixed number of $m$ distinct radii $ρ_1,ρ_2,...,ρ_m$, we show that the worst-case combinatorial complexity of the convex hull $CH_d(Σ)$ of $Σ$ is $Θ(\sum_{1\le{}i\ne{}j\le{}m}n_in_j^{\lfloor\frac{d}{2}\rfloor})$, where $n_i$ is the number of spheres in $Σ$ with radius $ρ_i$. To prove the lower bound, we construct a set of $Θ(n_1+n_2)$ spheres in $\mathbb{E}^d$, with $d\ge{}3$ odd, where $n_i$ spheres have radius $ρ_i$, $i=1,2$, and $ρ_2\neρ_1$, such that their convex hull has combinatorial complexity $Ω(n_1n_2^{\lfloor\frac{d}{2}\rfloor}+n_2n_1^{\lfloor\frac{d}{2}\rfloor})$. Our construction is then generalized to the case where the spheres have $m\ge{}3$ distinct radii. For the upper bound, we reduce the sphere convex hull problem to the problem of computing the worst-case combinatorial complexity of the convex hull of a set of $m$ $d$-dimensional convex polytopes lying on $m$ parallel hyperplanes in $\mathbb{E}^{d+1}$, where $d\ge{}3$ odd, a problem which is of independent interest. More precisely, we show that the worst-case combinatorial complexity of the convex hull of a set $\{\mathcal{P}_1,\mathcal{P}_2,...,\mathcal{P}_m\}$ of $m$ $d$-dimensional convex polytopes lying on $m$ parallel hyperplanes of $\mathbb{E}^{d+1}$ is $O(\sum_{1\le{}i\ne{}j\le{}m}n_in_j^{\lfloor\frac{d}{2}\rfloor})$, where $n_i$ is the number of vertices of $\mathcal{P}_i$. We end with algorithmic considerations, and we show how our tight bounds for the parallel polytope convex hull problem, yield tight bounds on the combinatorial complexity of the Minkowski sum of two convex polytopes in $\mathbb{E}^d$.
Thresholded Covering Algorithms for Robust and Max-Min Optimization
Venue: arXiv cs.DS 2011
Year: 2011

The general problem of robust optimization is this: one of several possible scenarios will appear tomorrow, but things are more expensive tomorrow than they are today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? Feige et al. and Khandekar et al. considered the k-robust model where the possible outcomes tomorrow are given by all demand-subsets of size k, and gave algorithms for the set cover problem, and the Steiner tree and facility location problems in this model, respectively. In this paper, we give the following simple and intuitive template for k-robust problems: "having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat". In this paper we show that this template gives us improved approximation algorithms for k-robust Steiner tree and set cover, and the first approximation algorithms for k-robust Steiner forest, minimum-cut and multicut. All our approximation ratios (except for multicut) are almost best possible. As a by-product of our techniques, we also get algorithms for max-min problems of the form: "given a covering problem instance, which k of the elements are costliest to cover?".
Point-to-point and Point-to-multipoint CDMA Access Network with Enhanced Security
Venue: arXiv cs.NI 2011
Year: 2011

We propose a network implementation with enhanced security at the physical layer by means of time-hopping CDMA, supporting cryptographically secure point-to-point and point-to-multipoint communication. In particular, we analyze an active star topology optical network implementation capable of supporting 128 simultaneous users up to 20 km apart. The feasibility of the proposed scheme is demonstrated through numerical simulation.
New Constructive Aspects of the Lovasz Local Lemma
Venue: arXiv cs.DS 2011
Year: 2011

The Lovász Local Lemma (LLL) states that the probability that none of a set of "bad" events happens is nonzero if the probability of each event is small compared to the number of bad events it depends on. A series of results have provided algorithms to efficiently construct structures whose existence is (non-constructively) guaranteed by the full asymmetric LLL, culminating in the recent breakthrough of Moser & Tardos. We show that the output distribution of the Moser-Tardos procedure has sufficient randomness, leading to two classes of algorithmic applications. We first show that when an LLL application provides a small amount of slack, the running time of the Moser-Tardos algorithm is polynomial in the number of underlying independent variables (not events!), and can thus be used to give efficient constructions in cases where the underlying proof applies the LLL to super-polynomially many events (or where finding a bad event that holds is computationally hard). We demonstrate our method on applications including: the first constant-factor approximation algorithm for the Santa Claus problem, as well as efficient algorithms for acyclic edge coloring, non-repetitive graph colorings, and Ramsey-type graphs. Second, we show applications to cases where a few of the bad events can hold, leading to the first such algorithmic applications of the LLL: MAX $k$-SAT is an illustrative example of this.
Steps towards a theory and calculus of aliasing
Venue: arXiv cs.SE 2011
Year: 2011

A theory, graphical notation, mathematical calculus and implementation for finding whether two given expressions can, at execution time, denote references attached to the same object. Intended as the basis for a comprehensive solution to the "frame problem" and as a complement to, or even a replacement for, separation logic, shape analysis, ownership types and dynamic frames.
Weight Optimization for Distributed Average Consensus Algorithm in Symmetric, CCS & KCS Star Networks
Venue: arXiv cs.IT 2011
Year: 2011

This paper addresses weight optimization problem in distributed consensus averaging algorithm over networks with symmetric star topology. We have determined optimal weights and convergence rate of the network in terms of its topological parameters. In addition, two alternative topologies with more rapid convergence rates have been introduced. The new topologies are Complete-Cored Symmetric (CCS) star and K-Cored Symmetric (KCS) star topologies. It has been shown that the optimal weights for the edges of central part in symmetric and CCS star configurations are independent of their branches. By simulation optimality of obtained weights under quantization constraints have been verified.
Training Over Sparse Multipath Channels in the Low SNR Regime
Venue: arXiv cs.IT 2011
Year: 2011

Training over sparse multipath channels is explored. The energy allocation and the optimal shape of training signals that enable error free communications over unknown channels are characterized as a function of the channels' statistics. The performance of training is evaluated by the reduction of the mean square error of the channel estimate and by the decrease in the uncertainty of the channel. A connection between the entropy of the wideband channel and the required energy for training is shown. In addition, there is a linkage between the sparsity and the entropy of the channel to the number of required channel measurements when the training is based on compressed sensing. The ability to learn the channel from few measurements is connected to the low entropy of sparse channels that enables training in the low SNR regime.
The Complexity of Flood Filling Games
Venue: arXiv cs.DS 2011
Year: 2011

We study the complexity of the popular one player combinatorial game known as Flood-It. In this game the player is given an n by n board of tiles where each tile is allocated one of c colours. The goal is to make the colours of all tiles equal via the shortest possible sequence of flooding operations. In the standard version, a flooding operation consists of the player choosing a colour k, which then changes the colour of all the tiles in the monochromatic region connected to the top left tile to k. After this operation has been performed, neighbouring regions which are already of the chosen colour k will then also become connected, thereby extending the monochromatic region of the board. We show that finding the minimum number of flooding operations is NP-hard for c>=3 and that this even holds when the player can perform flooding operations from any position on the board. However, we show that this "free" variant is in P for c=2. We also prove that for an unbounded number of colours, Flood-It remains NP-hard for boards of height at least 3, but is in P for boards of height 2. Next we show how a c-1 approximation and a randomised 2c/3 approximation algorithm can be derived, and that no polynomial time constant factor, independent of c, approximation algorithm exists unless P=NP. We then investigate how many moves are required for the "most demanding" n by n boards (those requiring the most moves) and show that the number grows as fast as Theta(n*c^0.5). Finally, we consider boards where the colours of the tiles are chosen at random and show that for c>=2, the number of moves required to flood the whole board is Omega(n) with high probability.
X-Armed Bandits
Venue: arXiv cs.LG 2011
Year: 2011

We consider a generalization of stochastic bandits where the set of arms, $\cX$, is allowed to be a generic measurable space and the mean-payoff function is "locally Lipschitz" with respect to a dissimilarity function that is known to the decision maker. Under this condition we construct an arm selection policy, called HOO (hierarchical optimistic optimization), with improved regret bounds compared to previous results for a large class of problems. In particular, our results imply that if $\cX$ is the unit hypercube in a Euclidean space and the mean-payoff function has a finite number of global maxima around which the behavior of the function is locally continuous with a known smoothness degree, then the expected regret of HOO is bounded up to a logarithmic factor by $\sqrt{n}$, i.e., the rate of growth of the regret is independent of the dimension of the space. We also prove the minimax optimality of our algorithm when the dissimilarity is a metric. Our basic strategy has quadratic computational complexity as a function of the number of time steps and does not rely on the doubling trick. We also introduce a modified strategy, which relies on the doubling trick but runs in linearithmic time. Both results are improvements with respect to previous approaches.
Interference Decoding for Deterministic Channels
Venue: arXiv cs.IT 2011
Year: 2011

An inner bound to the capacity region of a class of deterministic interference channels with three user pairs is presented. The key idea is to simultaneously decode the combined interference signal and the intended message at each receiver. It is shown that this interference-decoding inner bound is tight under certain strong interference conditions. The inner bound is also shown to strictly contain the inner bound obtained by treating interference as noise, which includes interference alignment for deterministic channels. The gain comes from judicious analysis of the number of combined interference sequences in different regimes of input distributions and message rates. Finally, the inner bound is generalized to the case where each channel output is observed through a noisy channel.
Lower Bounds for the Complexity of Monadic Second-Order Logic
Venue: arXiv cs.LO 2011
Year: 2011

Courcelle's famous theorem from 1990 states that any property of graphs definable in monadic second-order logic (MSO) can be decided in linear time on any class of graphs of bounded treewidth, or in other words, MSO is fixed-parameter tractable in linear time on any such class of graphs. From a logical perspective, Courcelle's theorem establishes a sufficient condition, or an upper bound, for tractability of MSO-model checking. Whereas such upper bounds on the complexity of logics have received significant attention in the literature, almost nothing is known about corresponding lower bounds. In this paper we establish a strong lower bound for the complexity of monadic second-order logic. In particular, we show that if C is any class of graphs which is closed under taking subgraphs and whose treewidth is not bounded by a polylogarithmic function (in fact, $\log^c n$ for some small c suffices) then MSO-model checking is intractable on C (under a suitable assumption from complexity theory).
High-Dimensional Matched Subspace Detection When Data are Missing
Venue: arXiv cs.IT 2011
Year: 2011

We consider the problem of deciding whether a highly incomplete signal lies within a given subspace. This problem, Matched Subspace Detection, is a classical, well-studied problem when the signal is completely observed. High- dimensional testing problems in which it may be prohibitive or impossible to obtain a complete observation motivate this work. The signal is represented as a vector in R^n, but we only observe m << n of its elements. We show that reliable detection is possible, under mild incoherence conditions, as long as m is slightly greater than the dimension of the subspace in question.
Computational limits to nonparametric estimation for ergodic processes
Venue: arXiv cs.IT 2011
Year: 2011

A new negative result for nonparametric estimation of binary ergodic processes is shown. I The problem of estimation of distribution with any degree of accuracy is studied. Then it is shown that for any countable class of estimators there is a zero-entropy binary ergodic process that is inconsistent with the class of estimators. Our result is different from other negative results for universal forecasting scheme of ergodic processes.
The relational model is injective for Multiplicative Exponential Linear Logic (without weakenings)
Venue: arXiv cs.LO 2011
Year: 2011

We show that for Multiplicative Exponential Linear Logic (without weakenings) the syntactical equivalence relation on proofs induced by cut-elimination coincides with the semantic equivalence relation on proofs induced by the multiset based relational model: one says that the interpretation in the model (or the semantics) is injective. We actually prove a stronger result: two cut-free proofs of the full multiplicative and exponential fragment of linear logic whose interpretations coincide in the multiset based relational model are the same "up to the connections between the doors of exponential boxes".
Contextual Bandit Algorithms with Supervised Learning Guarantees
Venue: arXiv cs.LG 2011
Year: 2011

We address the problem of learning in an online, bandit setting where the learner must repeatedly select among $K$ actions, but only receives partial feedback based on its choices. We establish two new facts: First, using a new algorithm called Exp4.P, we show that it is possible to compete with the best in a set of $N$ experts with probability $1-δ$ while incurring regret at most $O(\sqrt{KT\ln(N/δ)})$ over $T$ time steps. The new algorithm is tested empirically in a large-scale, real-world dataset. Second, we give a new algorithm called VE that competes with a possibly infinite set of policies of VC-dimension $d$ while incurring regret at most $O(\sqrt{T(d\ln(T) + \ln (1/δ))})$ with probability $1-δ$. These guarantees improve on those of all previous algorithms, whether in a stochastic or adversarial environment, and bring us closer to providing supervised learning type guarantees for the contextual bandit setting.
Joint Subcarrier Pairing and Power Allocation for OFDM Transmission with Decode-and-Forward Relaying
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, a point-to-point Orthogonal Frequency Division Multiplexing (OFDM) system with a decode-and-forward (DF) relay is considered. The transmission consists of two hops. The source transmits in the first hop, and the relay transmits in the second hop. Each hop occupies one time slot. The relay is half-duplex, and capable of decoding the message on a particular subcarrier in one time slot, and re-encoding and forwarding it on a different subcarrier in the next time slot. Thus each message is transmitted on a pair of subcarriers in two hops. It is assumed that the destination is capable of combining the signals from the source and the relay pertaining to the same message. The goal is to maximize the weighted sum rate of the system by jointly optimizing subcarrier pairing and power allocation on each subcarrier in each hop. The weighting of the rates is to take into account the fact that different subcarriers may carry signals for different services. Both total and individual power constraints for the source and the relay are investigated. For the situations where the relay does not transmit on some subcarriers because doing so does not improve the weighted sum rate, we further allow the source to transmit new messages on these idle subcarriers. To the best of our knowledge, such a joint optimization inclusive of the destination combining has not been discussed in the literature. The problem is first formulated as a mixed integer programming problem. It is then transformed to a convex optimization problem by continuous relaxation, and solved in the dual domain. Based on the optimization results, algorithms to achieve feasible solutions are also proposed. Simulation results show that the proposed algorithms almost achieve the optimal weighted sum rate, and outperform the existing methods in various channel conditions.
A logical basis for constructive systems
Venue: arXiv cs.LO 2011
Year: 2011

The work is devoted to Computability Logic (CoL) -- the philosophical/mathematical platform and long-term project for redeveloping classical logic after replacing truth} by computability in its underlying semantics (see http://www.cis.upenn.edu/~giorgi/cl.html). This article elaborates some basic complexity theory for the CoL framework. Then it proves soundness and completeness for the deductive system CL12 with respect to the semantics of CoL, including the version of the latter based on polynomial time computability instead of computability-in-principle. CL12 is a sequent calculus system, where the meaning of a sequent intuitively can be characterized as "the succedent is algorithmically reducible to the antecedent", and where formulas are built from predicate letters, function letters, variables, constants, identity, negation, parallel and choice connectives, and blind and choice quantifiers. A case is made that CL12 is an adequate logical basis for constructive applied theories, including complexity-oriented ones.
Innovation Rate Sampling of Pulse Streams with Application to Ultrasound Imaging
Venue: arXiv cs.IT 2011
Year: 2011

Signals comprised of a stream of short pulses appear in many applications including bio-imaging and radar. The recent finite rate of innovation framework, has paved the way to low rate sampling of such pulses by noticing that only a small number of parameters per unit time are needed to fully describe these signals. Unfortunately, for high rates of innovation, existing sampling schemes are numerically unstable. In this paper we propose a general sampling approach which leads to stable recovery even in the presence of many pulses. We begin by deriving a condition on the sampling kernel which allows perfect reconstruction of periodic streams from the minimal number of samples. We then design a compactly supported class of filters, satisfying this condition. The periodic solution is extended to finite and infinite streams, and is shown to be numerically stable even for a large number of pulses. High noise robustness is also demonstrated when the delays are sufficiently separated. Finally, we process ultrasound imaging data using our techniques, and show that substantial rate reduction with respect to traditional ultrasound sampling schemes can be achieved.