OpenRaiser/Intern-Atlas huggingface dataset:
Synthesizing Minimal Tile Sets for Patterned DNA Self-Assembly
Venue: arXiv cs.DS 2010
Year: 2010

The Pattern self-Assembly Tile set Synthesis (PATS) problem is to determine a set of coloured tiles that self-assemble to implement a given rectangular colour pattern. We give an exhaustive branch-and-bound algorithm to find tile sets of minimum cardinality for the PATS problem. Our algorithm makes use of a search tree in the lattice of partitions of the ambient rectangular grid, and an efficient bounding function to prune this search tree. Empirical data on the performance of the algorithm shows that it compares favourably to previously presented heuristic solutions to the problem.
A two-level logic approach to reasoning about computations
Venue: arXiv cs.LO 2010
Year: 2010

Relational descriptions have been used in formalizing diverse computational notions, including, for example, operational semantics, typing, and acceptance by non-deterministic machines. We therefore propose a (restricted) logical theory over relations as a language for specifying such notions. Our specification logic is further characterized by an ability to explicitly treat binding in object languages. Once such a logic is fixed, a natural next question is how we might prove theorems about specifications written in it. We propose to use a second logic, called a reasoning logic, for this purpose. A satisfactory reasoning logic should be able to completely encode the specification logic. Associated with the specification logic are various notions of binding: for quantifiers within formulas, for eigenvariables within sequents, and for abstractions within terms. To provide a natural treatment of these aspects, the reasoning logic must encode binding structures as well as their associated notions of scope, free and bound variables, and capture-avoiding substitution. Further, to support arguments about provability, the reasoning logic should possess strong mechanisms for constructing proofs by induction and co-induction. We provide these capabilities here by using a logic called G which represents relations over lambda-terms via definitions of atomic judgments, contains inference rules for induction and co-induction, and includes a special generic quantifier. We show how provability in the specification logic can be transparently encoded in G. We also describe an interactive theorem prover called Abella that implements G and this two-level logic approach and we present several examples that demonstrate the efficacy of Abella in reasoning about computations.
Efficient Distributed Random Walks with Applications
Venue: arXiv cs.DC 2010
Year: 2010

We focus on the problem of performing random walks efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain a random walk sample. We first present a fast sublinear time distributed algorithm for performing random walks whose time complexity is sublinear in the length of the walk. Our algorithm performs a random walk of length $\ell$ in $\tilde{O}(\sqrt{\ell D})$ rounds (with high probability) on an undirected network, where $D$ is the diameter of the network. This improves over the previous best algorithm that ran in $\tilde{O}(\ell^{2/3}D^{1/3})$ rounds (Das Sarma et al., PODC 2009). We further extend our algorithms to efficiently perform $k$ independent random walks in $\tilde{O}(\sqrt{k\ell D} + k)$ rounds. We then show that there is a fundamental difficulty in improving the dependence on $\ell$ any further by proving a lower bound of $Ω(\sqrt{\frac{\ell}{\log \ell}} + D)$ under a general model of distributed random walk algorithms. Our random walk algorithms are useful in speeding up distributed algorithms for a variety of applications that use random walks as a subroutine. We present two main applications. First, we give a fast distributed algorithm for computing a random spanning tree (RST) in an arbitrary (undirected) network which runs in $\tilde{O}(\sqrt{m}D)$ rounds (with high probability; here $m$ is the number of edges). Our second application is a fast decentralized algorithm for estimating mixing time and related parameters of the underlying network. Our algorithm is fully decentralized and can serve as a building block in the design of topologically-aware networks.
Automated Proofs in Geometry : Computing Upper Bounds for the Heilbronn Problem for Triangles
Venue: arXiv cs.CG 2010
Year: 2010

We propose a method for computing upper bounds for the Heilbronn problem for triangles.
Interval edge colorings of some products of graphs
Venue: arXiv cs.DM 2010
Year: 2010

An edge coloring of a graph $G$ with colors $1,2,\ldots ,t$ is called an interval $t$-coloring if for each $i\in \{1,2,\ldots,t\}$ there is at least one edge of $G$ colored by $i$, and the colors of edges incident to any vertex of $G$ are distinct and form an interval of integers. A graph $G$ is interval colorable, if there is an integer $t\geq 1$ for which $G$ has an interval $t$-coloring. Let $\mathfrak{N}$ be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if $G,H\in \mathfrak{N}$, then the Cartesian product of these graphs belongs to $\mathfrak{N}$. Also, they formulated a similar problem for the lexicographic product as an open problem. In this paper we first show that if $G\in \mathfrak{N}$, then $G[nK_{1}]\in \mathfrak{N}$ for any $n\in \mathbf{N}$. Furthermore, we show that if $G,H\in \mathfrak{N}$ and $H$ is a regular graph, then strong and lexicographic products of graphs $G,H$ belong to $\mathfrak{N}$. We also prove that tensor and strong tensor products of graphs $G,H$ belong to $\mathfrak{N}$ if $G\in \mathfrak{N}$ and $H$ is a regular graph.
A graph polynomial for independent sets of bipartite graphs
Venue: arXiv cs.DM 2010
Year: 2010

We introduce a new graph polynomial that encodes interesting properties of graphs, for example, the number of matchings and the number of perfect matchings. Most importantly, for bipartite graphs the polynomial encodes the number of independent sets (#BIS). We analyze the complexity of exact evaluation of the polynomial at rational points and show that for most points exact evaluation is #P-hard (assuming the generalized Riemann hypothesis) and for the rest of the points exact evaluation is trivial. We conjecture that a natural Markov chain can be used to approximately evaluate the polynomial for a range of parameters. The conjecture, if true, would imply an approximate counting algorithm for #BIS, a problem shown, by [Dyer et al. 2004], to be complete (with respect to, so called, AP-reductions) for a rich logically defined sub-class of #P. We give a mild support for our conjecture by proving that the Markov chain is rapidly mixing on trees. As a by-product we show that the "single bond flip" Markov chain for the random cluster model is rapidly mixing on constant tree-width graphs.
Finite Dimensional Statistical Inference
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we derive the explicit series expansion of the eigenvalue distribution of various models, namely the case of non-central Wishart distributions, as well as correlated zero mean Wishart distributions. The tools used extend those of the free probability framework, which have been quite successful for high dimensional statistical inference (when the size of the matrices tends to infinity), also known as free deconvolution. This contribution focuses on the finite Gaussian case and proposes algorithmic methods to compute the moments. Cases where asymptotic results fail to apply are also discussed.
LS-CS-residual (LS-CS): Compressive Sensing on Least Squares Residual
Venue: arXiv cs.IT 2010
Year: 2010

We consider the problem of recursively and causally reconstructing time sequences of sparse signals (with unknown and time-varying sparsity patterns) from a limited number of noisy linear measurements. The sparsity pattern is assumed to change slowly with time. The idea of our proposed solution, LS-CS-residual (LS-CS), is to replace compressed sensing (CS) on the observation by CS on the least squares (LS) residual computed using the previous estimate of the support. We bound CS-residual error and show that when the number of available measurements is small, the bound is much smaller than that on CS error if the sparsity pattern changes slowly enough. We also obtain conditions for "stability" of LS-CS over time for a signal model that allows support additions and removals, and that allows coefficients to gradually increase (decrease) until they reach a constant value (become zero). By "stability", we mean that the number of misses and extras in the support estimate remain bounded by time-invariant values (in turn implying a time-invariant bound on LS-CS error). The concept is meaningful only if the bounds are small compared to the support size. Numerical experiments backing our claims are shown.
A Theory of Sampling for Continuous-time Metric Temporal Logic
Venue: arXiv cs.LO 2010
Year: 2010

This paper revisits the classical notion of sampling in the setting of real-time temporal logics for the modeling and analysis of systems. The relationship between the satisfiability of Metric Temporal Logic (MTL) formulas over continuous-time models and over discrete-time models is studied. It is shown to what extent discrete-time sequences obtained by sampling continuous-time signals capture the semantics of MTL formulas over the two time domains. The main results apply to "flat" formulas that do not nest temporal operators and can be applied to the problem of reducing the verification problem for MTL over continuous-time models to the same problem over discrete-time, resulting in an automated partial practically-efficient discretization technique.
Tight Thresholds for Cuckoo Hashing via XORSAT
Venue: arXiv cs.DS 2010
Year: 2010

We settle the question of tight thresholds for offline cuckoo hashing. The problem can be stated as follows: we have n keys to be hashed into m buckets each capable of holding a single key. Each key has k >= 3 (distinct) associated buckets chosen uniformly at random and independently of the choices of other keys. A hash table can be constructed successfully if each key can be placed into one of its buckets. We seek thresholds alpha_k such that, as n goes to infinity, if n/m <= alpha for some alpha < alpha_k then a hash table can be constructed successfully with high probability, and if n/m >= alpha for some alpha > alpha_k a hash table cannot be constructed successfully with high probability. Here we are considering the offline version of the problem, where all keys and hash values are given, so the problem is equivalent to previous models of multiple-choice hashing. We find the thresholds for all values of k > 2 by showing that they are in fact the same as the previously known thresholds for the random k-XORSAT problem. We then extend these results to the setting where keys can have differing number of choices, and provide evidence in the form of an algorithm for a conjecture extending this result to cuckoo hash tables that store multiple keys in a bucket.
A boundary between universality and non-universality in spiking neural P systems
Venue: arXiv cs.CC 2010
Year: 2010

In this work we offer a significant improvement on the previous smallest spiking neural P systems and solve the problem of finding the smallest possible extended spiking neural P system. Paun and Paun gave a universal spiking neural P system with 84 neurons and another that has extended rules with 49 neurons. Subsequently, Zhang et al. reduced the number of neurons used to give universality to 67 for spiking neural P systems and to 41 for the extended model. Here we give a small universal spiking neural P system that has only 17 neurons and another that has extended rules with 5 neurons. All of the above mentioned spiking neural P systems suffer from an exponential slow down when simulating Turing machines. Using a more relaxed encoding technique we get a universal spiking neural P system that has extended rules with only 4 neurons. This latter spiking neural P system simulates 2-counter machines in linear time and thus suffer from a double exponential time overhead when simulating Turing machines. We show that extended spiking neural P systems with 3 neurons are simulated by log-space bounded Turing machines, and so there exists no such universal system with 3 neurons. It immediately follows that our 4-neuron system is the smallest possible extended spiking neural P system that is universal. Finally, we show that if we generalise the output technique we can give a universal spiking neural P system with extended rules that has only 3 neurons. This system is also the smallest of its kind as a universal spiking neural P system with extended rules and generalised output is not possible with 2 neurons.
Communication Complexity and Intrinsic Universality in Cellular Automata
Venue: arXiv cs.DM 2010
Year: 2010

The notions of universality and completeness are central in the theories of computation and computational complexity. However, proving lower bounds and necessary conditions remains hard in most of the cases. In this article, we introduce necessary conditions for a cellular automaton to be "universal", according to a precise notion of simulation, related both to the dynamics of cellular automata and to their computational power. This notion of simulation relies on simple operations of space-time rescaling and it is intrinsic to the model of cellular automata. Intrinsinc universality, the derived notion, is stronger than Turing universality, but more uniform, and easier to define and study. Our approach builds upon the notion of communication complexity, which was primarily designed to study parallel programs, and thus is, as we show in this article, particulary well suited to the study of cellular automata: it allowed to show, by studying natural problems on the dynamics of cellular automata, that several classes of cellular automata, as well as many natural (elementary) examples, could not be intrinsically universal.
Is Ramsey's theorem omega-automatic?
Venue: arXiv cs.LO 2010
Year: 2010

We study the existence of infinite cliques in omega-automatic (hyper-)graphs. It turns out that the situation is much nicer than in general uncountable graphs, but not as nice as for automatic graphs. More specifically, we show that every uncountable omega-automatic graph contains an uncountable co-context-free clique or anticlique, but not necessarily a context-free (let alone regular) clique or anticlique. We also show that uncountable omega-automatic ternary hypergraphs need not have uncountable cliques or anticliques at all.
Robust Fault Tolerant uncapacitated facility location
Venue: arXiv cs.DS 2010
Year: 2010

In the uncapacitated facility location problem, given a graph, a set of demands and opening costs, it is required to find a set of facilities R, so as to minimize the sum of the cost of opening the facilities in R and the cost of assigning all node demands to open facilities. This paper concerns the robust fault-tolerant version of the uncapacitated facility location problem (RFTFL). In this problem, one or more facilities might fail, and each demand should be supplied by the closest open facility that did not fail. It is required to find a set of facilities R, so as to minimize the sum of the cost of opening the facilities in R and the cost of assigning all node demands to open facilities that did not fail, after the failure of up to αfacilities. We present a polynomial time algorithm that yields a 6.5-approximation for this problem with at most one failure and a 1.5 + 7.5α-approximation for the problem with at most α> 1 failures. We also show that the RFTFL problem is NP-hard even on trees, and even in the case of a single failure.
The complexity of the list homomorphism problem for graphs
Venue: arXiv cs.CC 2010
Year: 2010

We completely classify the computational complexity of the list H-colouring problem for graphs (with possible loops) in combinatorial and algebraic terms: for every graph H the problem is either NP-complete, NL-complete, L-complete or is first-order definable; descriptive complexity equivalents are given as well via Datalog and its fragments. Our algebraic characterisations match important conjectures in the study of constraint satisfaction problems.
The skewness of computer science
Venue: arXiv cs.DL 2010
Year: 2010

Computer science is a relatively young discipline combining science, engineering, and mathematics. The main flavors of computer science research involve the theoretical development of conceptual models for the different aspects of computing and the more applicative building of software artifacts and assessment of their properties. In the computer science publication culture, conferences are an important vehicle to quickly move ideas, and journals often publish deeper versions of papers already presented at conferences. These peculiarities of the discipline make computer science an original research field within the sciences, and, therefore, the assessment of classical bibliometric laws is particularly important for this field. In this paper, we study the skewness of the distribution of citations to papers published in computer science publication venues (journals and conferences). We find that the skewness in the distribution of mean citedness of different venues combines with the asymmetry in citedness of articles in each venue, resulting in a highly asymmetric citation distribution with a power law tail. Furthermore, the skewness of conference publications is more pronounced than the asymmetry of journal papers. Finally, the impact of journal papers, as measured with bibliometric indicators, largely dominates that of proceeding papers.
Optimizing Histogram Queries under Differential Privacy
Venue: arXiv cs.DB 2010
Year: 2010

Differential privacy is a robust privacy standard that has been successfully applied to a range of data analysis tasks. Despite much recent work, optimal strategies for answering a collection of correlated queries are not known. We study the problem of devising a set of strategy queries, to be submitted and answered privately, that will support the answers to a given workload of queries. We propose a general framework in which query strategies are formed from linear combinations of counting queries, and we describe an optimal method for deriving new query answers from the answers to the strategy queries. Using this framework we characterize the error of strategies geometrically, and we propose solutions to the problem of finding optimal strategies.
Cognitive MAC Protocols Using Memory for Distributed Spectrum Sharing Under Limited Spectrum Sensing
Venue: arXiv cs.NI 2010
Year: 2010

The main challenges of cognitive radio include spectrum sensing at the physical (PHY) layer to detect the activity of primary users and spectrum sharing at the medium access control (MAC) layer to coordinate access among coexisting secondary users. In this paper, we consider a cognitive radio network in which a primary user shares a channel with secondary users that cannot distinguish the signals of the primary user from those of a secondary user. We propose a class of distributed cognitive MAC protocols to achieve efficient spectrum sharing among the secondary users while protecting the primary user from potential interference by the secondary users. By using a MAC protocol with one-slot memory, we can obtain high channel utilization by the secondary users while limiting interference to the primary user at a low level. The results of this paper suggest the possibility of utilizing MAC design in cognitive radio networks to overcome limitations in spectrum sensing at the PHY layer as well as to achieve spectrum sharing at the MAC layer.
LoopW Technical Reference v0.3
Venue: arXiv cs.LO 2010
Year: 2010

This document describes the implementation in SML of the LoopW language, an imperative language with higher-order procedural variables and non-local jumps equiped with a program logic. It includes the user manual along with some implementation notes and many examples of certified imperative programs. As a concluding example, we show the certification of an imperative program encoding shift/reset using callcc/throw and a global meta-continuation.
Computing the Least Fixed Point of Positive Polynomial Systems
Venue: arXiv cs.NA 2010
Year: 2010

We consider equation systems of the form X_1 = f_1(X_1, ..., X_n), ..., X_n = f_n(X_1, ..., X_n) where f_1, ..., f_n are polynomials with positive real coefficients. In vector form we denote such an equation system by X = f(X) and call f a system of positive polynomials, short SPP. Equation systems of this kind appear naturally in the analysis of stochastic models like stochastic context-free grammars (with numerous applications to natural language processing and computational biology), probabilistic programs with procedures, web-surfing models with back buttons, and branching processes. The least nonnegative solution mu f of an SPP equation X = f(X) is of central interest for these models. Etessami and Yannakakis have suggested a particular version of Newton's method to approximate mu f. We extend a result of Etessami and Yannakakis and show that Newton's method starting at 0 always converges to mu f. We obtain lower bounds on the convergence speed of the method. For so-called strongly connected SPPs we prove the existence of a threshold k_f such that for every i >= 0 the (k_f+i)-th iteration of Newton's method has at least i valid bits of mu f. The proof yields an explicit bound for k_f depending only on syntactic parameters of f. We further show that for arbitrary SPP equations Newton's method still converges linearly: there are k_f>=0 and alpha_f>0 such that for every i>=0 the (k_f+alpha_f i)-th iteration of Newton's method has at least i valid bits of mu f. The proof yields an explicit bound for alpha_f; the bound is exponential in the number of equations, but we also show that it is essentially optimal. Constructing a bound for k_f is still an open problem. Finally, we also provide a geometric interpretation of Newton's method for SPPs.
Orthogonal vs Non-Orthogonal Multiple Access with Finite Input Alphabet and Finite Bandwidth
Venue: arXiv cs.IT 2010
Year: 2010

For a two-user Gaussian multiple access channel (GMAC), frequency division multiple access (FDMA), a well known orthogonal-multiple-access (O-MA) scheme has been preferred to non-orthogonal-multiple-access (NO-MA) schemes since FDMA can achieve the sum-capacity of the channel with only single-user decoding complexity [\emph{Chapter 14, Elements of Information Theory by Cover and Thomas}]. However, with finite alphabets, in this paper, we show that NO-MA is better than O-MA for a two-user GMAC. We plot the constellation constrained (CC) capacity regions of a two-user GMAC with FDMA and time division multiple access (TDMA) and compare them with the CC capacity regions with trellis coded multiple access (TCMA), a recently introduced NO-MA scheme. Unlike the Gaussian alphabets case, it is shown that the CC capacity region with FDMA is strictly contained inside the CC capacity region with TCMA. In particular, for a given bandwidth, the gap between the CC capacity regions with TCMA and FDMA is shown to increase with the increase in the average power constraint. Also, for a given power constraint, the gap between the CC capacity regions with TCMA and FDMA is shown to decrease with the increase in the bandwidth. Hence, for finite alphabets, a NO-MA scheme such as TCMA is better than the well known O-MAC schemes, FDMA and TDMA which makes NO-MA schemes worth pursuing in practice for a two-user GMAC.