A decidable characterization of the classes between lintime and exptime

A language is defined by closure under safe iteration and under a new form of safe diagonalization that, unlike other forms of diagonalization used in literature to define sub-recursive hierarchies, is constructive and decidable. By counting the nesting levels of these schemes, an ordinal is assigned to each program. This yields a hierarchy Tα(α<ωω) that singles-out the complexity classes DTIMEF(ncnd+e) for all c,d,e?0.     

String matching with simple devices

With the help of a general simulation technique of deterministic finite two-way multi-head automata by automata with blind heads we show O(n²/logn) to be an upper time bound on string matching. This result is tight by a previously known lower bound.     

Orthogonal queries in segments

We consider theorthgonal clipping problem in a set of segments: Given a set ofn segments ind-dimensional space, we preprocess them into a data structure such that given an orthogonal query window, the segments intersecting it can be counted/reported efficiently. We show that the efficiency of the data structure significantly depends on a geometric discrete parameterK named theProjected-image complexity, which becomes Θ(n ²) in the worst case but practically much smaller. If we useO(m) space, whereK log^4d−7 n≥m≥n log^4d−7 n, the query time isO((K/m)^1/2 log^{max{4, 4d−5}} n). This is near to an Ω((K/m)^1/2) lower bound.     

Nearly-perfect hypergraph packing is in NC

Answering a question of Rödl and Thoma, we show that the Nibble Algorithm for finding a collection of disjoint edges covering almost all vertices in an almost regular, uniform hypergraph with negligible pair degrees can be derandomized and parallelized to run in polylog time on polynomially many parallel processors. In other words, the nearly-perfect packing problem on this class of hypergraphs is in the complexity class NC.     

Monotone circuits for monotone weighted threshold functions

Weighted threshold functions with positive weights are a natural generalization of unweighted threshold functions. These functions are clearly monotone. However, the naive way of computing them is adding the weights of the satisfied variables and checking if the sum is greater than the threshold; this algorithm is inherently non-monotone since addition is a non-monotone function. In this work we by-pass this addition step and construct a polynomial size logarithmic depth unbounded fan-in monotone circuit for every weighted threshold function, i.e., we show that weighted threshold functions are in mAC¹. (To the best of our knowledge, prior to our work no polynomial monotone circuits were known for weighted threshold functions.)Our monotone circuits are applicable for the cryptographic tool of secret sharing schemes. Using general results for compiling monotone circuits (Yao, 1989) and monotone formulae (Benaloh and Leichter, 1990) into secret sharing schemes, we get secret sharing schemes for every weighted threshold access structure. Specifically, we get: (1) information-theoretic secret sharing schemes where the size of each share is quasi-polynomial in the number of users, and (2) computational secret sharing schemes where the size of each share is polynomial in the number of users.     

A meeting scheduling problem respecting time and space

We consider the problem of determining suitable meeting times and locations for a group of participants wishing to schedule a new meeting subject to already scheduled meetings possibly held at a number of different locations. Each participant must be able to reach the new meeting location, attend for the entire duration, and reach the next meeting location on time. In particular, we give two solutions to the problem instance where each participant has two scheduled meetings separated by a free time interval. We present an O(n logn) algorithm for n participants obtained by purely geometrical arguments. Our second approach uses the concept of LP-type problems and leads to a randomized algorithm with expected running time O(n). We also consider a graph-based model where participants belong to different groups and can travel along the edges of a graph. For the meeting, only one member out of each group is required. The resulting problem can be solved using furthest color Voronoi diagrams on graphs.

Lower bounds on the OBDD size of two fundamental functions' graphs

Ordered Binary Decision Diagrams (OBDDs) are a data structure for Boolean functions which supports many useful operations. Among others it finds applications in CAD, model checking, and symbolic graph algorithms. Nevertheless, many simple functions are known to have exponential OBDD size with respect to their number of variables. In order to investigate the limits of symbolic graph algorithms which work on OBDD-represented graph instances, it is useful to have simply-structured graphs whose OBDD representation has exponential size. Therefore, we consider two fundamental functions with exponential lower bounds on their OBDD size and transfer these results to their corresponding graphs. Concretely, we consider the Indirect Storage Access function and the Hidden Weighted Bit function.     

A characterization of average case communication complexity

It is well known that the average case deterministic communication complexity is bounded below by an entropic quantity, which one would now call deterministic information complexity. In this paper we show a corresponding upper bound. We also improve known lower bounds for the public coin Las Vegas communication complexity by a constant factor.     

Arbitrary sequence RAMs

It is known that in some cases a Random Access Machine (RAM) benefits from having an additional input that is an arbitrary number, satisfying only the criterion of being sufficiently large. This is known as the ARAM model. We introduce a new type of RAM, which we refer to as the Arbitrary Sequence RAM (ASRAM), that generalises the ARAM by allowing the generation of additional arbitrary large numbers at will during execution time. We characterise the power contribution of this ability under several RAM variants.     

Probabilistic weak simulation is decidable in polynomial time

This paper considers a weak simulation preorder for Markov chains that allows for stuttering. Despite the second-order quantification in its definition, we present a polynomial-time algorithm to compute the weak simulation preorder of a finite Markov chain.     

Efficient evaluation of specific queries in constraint databases

Let F₁,…,Fs∈R[X₁,…,Xn] be polynomials of degree at most d, and suppose that F₁,…,Fs are represented by a division free arithmetic circuit of non-scalar complexity size L. Let A be the arrangement of Rn defined by F₁,…,Fs.For any point x∈Rn, we consider the task of determining the signs of the values F₁(x),…,Fs(x) (sign condition query) and the task of determining the connected component of A to which x belongs (point location query). By an extremely simple reduction to the well-known case where the polynomials F₁,…,Fs are affine linear (i.e., polynomials of degree one), we show first that there exists a database of (possibly enormous) size sO(L+n) which allows the evaluation of the sign condition query using only (Ln)^O(1)log(s) arithmetic operations. The key point of this paper is the proof that this upper bound is almost optimal.By the way, we show that the point location query can be evaluated using dO(n)log(s) arithmetic operations. Based on a different argument, analogous complexity upper-bounds are exhibited with respect to the bit-model in case that F₁,…,Fs belong to Z[X₁,…,Xn] and satisfy a certain natural genericity condition. Mutatis mutandis our upper-bound results may be applied to the sparse and dense representations of F₁,…,Fs.     

The frequent paucity of trivial strings

A 1976 theorem of Chaitin can be used to show that arbitrarily dense sets of lengths n have a paucity of trivial strings (only a bounded number of strings of length n having trivially low plain Kolmogorov complexities). We use the probabilistic method to give a new proof of this fact. This proof is much simpler than previously published proofs, and it gives a tighter paucity bound.     

Learning a subclass of k-quasi-Horn formulas with membership queries

Boolean formulas have been widely studied in the field of learning theory. We focus on the model of learning with queries, and study a restriction of the class of k-quasi-Horn formulas, that is, conjunctive normal form formulas where the number of unnegated literals per clause is at most k. This class is known to be as hard to learn as the general class CNF of conjunctive normal form formulas. By imposing some constraints, we define a fragment of this logic that can be learned using only membership queries. Also we prove that none of these constraints makes by itself the class learnable.     

Simulation of simultaneous safe recursion over an arbitrary structure

In [O. Bournez, F. Cucker, P.J. de Naurois, J.Y. Marion, Computability over an arbitrary structure. Sequential and parallel polynomial time, in: Lecture Notes in Computer Science, vol. 2620, Springer, Berlin, 2003, pp. 185-199] the class of safe recursive functions over an arbitrary structure is defined. A question of simulation of the simultaneous safe recursion by single safe recursion was set. We prove that this simulation is feasible using bounded coding and decoding functions.     

A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs

An edge ranking of a graph G is a labeling r of its edges with positive integers such that every path between two different edges eu, ev with the same rank r(eu)=r(ev) contains an intermediate edge ew with rank r(ew)>r(eu). An edge ranking of G is minimum if the largest rank k assigned is the smallest among all rankings of G. The edge ranking problem is to find a minimum edge ranking of given graph G. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of trees. In this paper, we first show, on a general graph G, a relation between a minimum edge ranking of G and its minimal cuts, which ensures that we can obtain a polynomial time algorithm for obtaining minimum edge ranking of a given graph G if minimal cuts for each subgraph of G can be found in polynomial time and the number of those is polynomial. Based on this relation, we develop a polynomial time algorithm for finding a minimum edge ranking on a 2-connected outerplanar graph.     

A note on compressed sensing and the complexity of matrix multiplication

We consider the conjectured O(N2+?) time complexity of multiplying any two N×N matrices A and B. Our main result is a deterministic Compressed Sensing (CS) algorithm that both rapidly and accurately computes A⋅B provided that the resulting matrix product is sparse/compressible. As a consequence of our main result we increase the class of matrices A, for any given N×N matrix B, which allows the exact computation of A⋅B to be carried out using the conjectured O(N2+?) operations. Additionally, in the process of developing our matrix multiplication procedure, we present a modified version of Indyk's recently proposed extractor-based CS algorithm [P. Indyk, Explicit constructions for compressed sensing of sparse signals, in: SODA, 2008] which is resilient to noise.     

Parameterized complexity and improved inapproximability for computing the largest j-simplex in a V-polytope

We consider the problem of computing the squared volume of the largest j-simplex contained in an n-dimensional polytope presented by its vertices (a V-polytope). We show that the related decision problem is W[1]-complete, with respect to the parameter j. We also improve the constant inapproximability factor given in [A. Packer, Polynomial-time approximation of largest simplices in V-polytopes, Discrete Appl. Math. 134 (1-3) (2004) 213-237], by showing that there are constants μ<1,c>1 such that it is NP-hard to approximate within a factor of cμn the volume of the largest ⌊μn⌋-simplex contained in an n-dimensional polytope with O(n) vertices.     

On the All-Farthest-Segments problem for a planar set of points

In this note, we outline a very simple algorithm for the following problem: Given a set S of n points p₁,p₂,p₃,…,pn in the plane, we have O(n²) segments implicitly defined on pairs of these n points. For each point pi, find a segment from this set of implicitly defined segments that is farthest from pi. The time complexity of our algorithm is in O(nh+nlogn), where n is the number of input points, and h is the number of vertices on the convex hull of S.     

A note on efficient aggregate queries in sensor networks

We consider a scenario where nodes in a sensor network hold numeric items, and the task is to evaluate simple functions of the distributed data. In this note we present distributed protocols for computing the median with sublinear space and communication complexity per node. Specifically, we give a deterministic protocol for computing median with polylog complexity and a randomized protocol that computes an approximate median with polyloglog communication complexity per node. On the negative side, we observe that any deterministic protocol that counts the number of distinct data items must have linear complexity in the worst case.     

The reachability problem for branching vector addition systems requires doubly-exponential space

Branching vector addition systems are an extension of vector addition systems where new reachable vectors may be obtained by summing two reachable vectors and adding an integral vector from a fixed finite set. The reachability problem for them is shown hard for doubly-exponential space. For an alternative extension of vector addition systems, where reachable vectors may be combined by subtraction, most decision problems of interest are shown undecidable.