The optimal read-once branching program complexity for the direct storage access function

Branching programs are computation models measuring the space of (Turing machine) computations. Read-once branching programs (BP1s) are the most general model where each graph-theoretical path is the computation path for some input. Exponential lower bounds on the size of read-once branching programs are known since a long time. Nevertheless, there are only few functions where the BP1 size is asymptotically known exactly. In this paper, the exact BP1 size of a fundamental function, the direct storage access function, is determined.     

A note on the decoding complexity of error-correcting codes

A time-space tradeoff lower bound for the decoding complexity of asymptotically good error-correcting codes for oblivious write-k-times branching programs is proved. Specifically, we prove that the computation time T and space S of every oblivious write-k-times branching program that decodes an asymptotically good error-correcting code with block length n satisfy S⋅Tk=Ω((n/k)^k+1).     

Lower bounds for monotone span programs

Span programs provide a linear algebraic model of computation. Lower bounds for span programs imply lower bounds for formula size, symmetric branching programs, and contact schemes. Monotone span programs correspond also to linear secret-sharing schemes. We present a new technique for proving lower bounds for monotone span programs. We prove a lower bound of (m ^2.5) for the 6-clique function. Our results improve on the previously known bounds for explicit functions.     

A nondeterministic space-time tradeoff for linear codes

We are interested in proving exponential lower bounds on the size of nondeterministic D-way branching programs computing functions in linear time, that is, in time at most kn for a constant k. Ajtai has proved such lower bounds for explicit functions over domains D of size about n, and Beame, Saks and Thathachar for functions over domains of size about k²². We prove an exponential lower bound ²Ω(n/ck) for an explicit function over substantially smaller domain D of size about k². Our function is a universal function of linear codes.     

A note on the size of OBDDs for the graph of integer multiplication

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations and ordered binary decision diagrams (OBDDs) are the most common dynamic data structure for Boolean functions. Among the many areas of application are verification, model checking, computer-aided design, relational algebra, and symbolic graph algorithms. Analyzing the limits of symbolic graph algorithms for the all-pairs-shortest paths problem which work on OBDD-represented graph instances the so-called graph of integer multiplication has been investigated by Sawitzki [D. Sawitzki, Lower bounds on the OBDD size of graphs of some popular functions, in: Proc. of SOFSEM, LNCS, vol. 3381, 2005, pp. 298-309]. Using simple arguments his lower bound of ²n/768−1 on the size of OBDDs representing the graph of integer multiplication is improved up to ²n/24.     

Larger lower bounds on the OBDD complexity of integer multiplication

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations and ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Recently, the question whether the OBDD complexity of the most significant bit of integer multiplication is exponential has been answered affirmatively. In this paper a larger general lower bound is presented using a simpler proof. Furthermore, we prove a larger lower bound for the variable order assumed to be one of the best ones for the most significant bit. Moreover, the best known lower bound on the OBDD complexity for the so-called graph of integer multiplication is improved.     

On the OBDD complexity of the most significant bit of integer multiplication

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations. Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for boolean functions. Among the many areas of application are verification, model checking, computer-aided design, relational algebra, and symbolic graph algorithms. In this paper it is shown that the OBDD complexity of the most significant bit of integer multiplication is exponential answering an open question posed by Wegener (2000) [18].     

A note on border rank

A closed condition for tensors of border rank ? r is given. Applied to the structural tensor <n, n, n,> of n × n matrix multiplication this criterion yields a $\text{3}\text{2}\text{n}{}^2\text{+}\text{1}\text{2}\text{n}\text{? 1}$ lower bound on its border rank.     

A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs

Branching programs are a well-established computation model for Boolean functions, especially read-once branching programs (BP1s) have been studied intensively. A very simple function f in n² variables is exhibited such that both the function f and its negation ¬f can be computed by Σ³_p-circuits, the function f has nondeterministic BP1s (with one nondeterministic node) of linear size and ¬f has size O(n⁴) for oblivious nondeterministic BP1s but f requires nondeterministic graph-driven BP1s of size . This answers an open question stated by Jukna, Razborov, Savický, and Wegener [Comput. Complexity 8 (1999) 357-370].     

Expanders and time-restricted branching programs

The replication number   of a branching program is the minimum number R$R$ such that along every accepting computation at most R$R$ variables are tested more than once; the sets of variables re-tested along different computations may be different. For every branching program, this number lies between 0$0$ (read-once programs) and the total number n$n$ of variables (general branching programs). The best results so far were exponential lower bounds on the size of branching programs with R=o(n/logn)$R=o(n/logn)$. We improve this to R≤?n$R\le ?n$ for a constant ?>0$?>0$. This also gives an alternative and simpler proof of an exponential lower bound for (1+?)n$(1+?)n$ time branching programs for a constant ?>0$?>0$. We prove these lower bounds for quadratic functions of Ramanujan graphs.     

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.     

A large lower bound on the query complexity of a simple boolean function

Combinatorial property testing, initiated formally by Goldreich, Goldwasser, and Ron (1998) and inspired by Rubinfeld and Sudan (1996), deals with the relaxation of decision problems. Given a property P the aim is to decide whether a given input satisfies the property P or is far from having the property. For a family of boolean functions f=(fn) the associated property is the set of 1-inputs of f. Here, the known lower bounds on the query complexity of properties identified by boolean functions representable by (very) restricted branching programs of small size is improved up to Ω(n1/2), where n is the input length.     

Exponential space complexity for OBDD-based reachability analysis

Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Nevertheless, many basic graph problems are known to be PSPACE-hard if their input graphs are represented by OBDDs. Computing the set of nodes that are reachable from some source s∈V in a digraph G=(V,E) is an important problem in computer-aided design, hardware verification, and model checking. Until now only exponential lower bounds on the space complexity of a restricted class of OBDD-based algorithms for the reachability problem have been known. Here, the result is extended by presenting an exponential lower bound for the general reachability problem. As a by-product a general exponential lower bound is obtained for the computation of OBDDs representing all connected node pairs in a graph, the transitive closure.     

New upper bounds on the Boolean circuit complexity of symmetric functions

In this note, we present improved upper bounds on the circuit complexity of symmetric Boolean functions. In particular, we describe circuits of size 4.5n+o(n) for any symmetric function of n variables, as well as circuits of size 3n for function.     

On uncertainty versus size in branching programs

We propose an information-theoretic approach to proving lower bounds on the size of branching programs. The argument is based on Kraft type inequalities for the average amount of uncertainty about (or entropy of) a given input during the various stages of computation. The uncertainty is measured by the average depth of so-called ‘splitting trees’ for sets of inputs reaching particular nodes of the program.

We first demonstrate the approach for read-once branching programs. Then, we introduce a strictly larger class of so-called ‘balanced’ branching programs and, using the suggested approach, prove that some explicit Boolean functions cannot be computed by balanced programs of polynomial size. These lower bounds are new since some explicit functions, which are known to be hard for most previously considered restricted classes of branching programs, can be easily computed by balanced branching programs of polynomial size.     

The complexity of synchronous iterative Do-All with crashes

The ability to cooperate on common tasks in a distributed setting is key to solving a broad range of computation problems ranging from distributed search such as SETI to distributed simulation and multi-agent collaboration. Do-All, an abstraction of such cooperative activity, is the problem of performing N tasks in a distributed system of P failure-prone processors. Many distributed and parallel algorithms have been developed for this problem and several algorithm simulations have been developed by iterating Do-All algorithms. The efficiency of the solutions for Do-All is measured in terms of work complexity where all processing steps taken by all processors are counted. Work is ideally expressed as a function of N, P, and f, the number of processor crashes. However the known lower bounds and the upper bounds for extant algorithms do not adequately show how work depends on f. We present the first non-trivial lower bounds for Do-All that capture the dependence of work on N, P and f. For the model of computation where processors are able to make perfect load-balancing decisions locally, we also present matching upper bounds. We define the r-iterative Do-All problem that abstracts the repeated use of Do-All such as found in typical algorithm simulations. Our f-sensitive analysis enables us to derive tight bounds for r-iterative Do-All work (that are stronger than the r-fold work complexity of a single Do-All). Our approach that models perfect load-balancing allows for the analysis of specific algorithms to be divided into two parts: (i) the analysis of the cost of tolerating failures while performing work under free load-balancing, and (ii) the analysis of the cost of implementing load-balancing. We demonstrate the utility and generality of this approach by improving the analysis of two known efficient algorithms. We give an improved analysis of an efficient message-passing algorithm. We also derive a tight and complete analysis of the best known Do-All algorithm for the synchronous shared-memory model. Finally we present a new upper bound on simulations of synchronous shared-memory algorithms on crash-prone processors.Received: 15 May 2002, Accepted: 15 June 2003, Published online: 6 February 2004This work is supported in part by the NSF TOC Grants 9988304 and 0311368, and the NSF ITR Grant 0121277. The work of the second author is supported in part by the NSF CAREER Award 0093065. The work of the third author is supported in part by the NSF CAREER Award 9984778.