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.     

A characterization of span program size and improved lower bounds for monotone span programs

We give a characterization of span program size by a combinatorial-algebraic measure. The measure we consider is a generalization of a measure on covers which has been used to prove lower bounds on formula size and has also been studied with respect to communication complexity.?In the monotone case our new methods yield lower bounds for the monotone span program complexity of explicit Boolean functions in n variables over arbitrary fields, improving the previous lower bounds on monotone span program size. Our characterization of span program size implies that any matrix with superpolynomial separation between its rank and cover number can be used to obtain superpolynomial lower bounds on monotone span program size. We also identify a property of bipartite graphs that is suficient for constructing Boolean functions with large monotone span program complexity. Received: September 30, 2000.     

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.     

Deciding branching time properties for asynchronous programs

Asynchronous programming is a paradigm that supports asynchronous function calls in addition to synchronous function calls. Programs in such a setting can be modeled by automata with counters that keep track of the number of pending asynchronous calls for each function, as well as a call stack for synchronous recursive computation. These programs have the restriction that an asynchronous call is processed only when the call stack is empty. The decidability of the control state reachability problem for such systems was recently established. In this paper, we consider the problems of checking other branching time properties for such systems. Specifically we consider the following problems — termination, which asks if there is an infinite (non-terminating) computation exhibited by the system; control state maintainability, which asks if there is a maximal execution of the system, where all the state visited lie in some “good” set; whether the system can be simulated by a given finite state system; and whether the system can simulate a given finite state system. We present decision algorithms for all these problems.     

On lower bounds for the complexity of polynomials and their multiples

We prove a theorem giving arbitrarily long explicit sequences of algebraic numbers such that any nonzero polynomial f(X) satisfying has nonscalar complexity for some positive constant C independent of s. A similar result is shown for rapidly growing rational sequences. Received: April 6 1999.     

Guaranteeing good memory bounds for parallel programs

The amount of memory required by a parallel program may be spectacularly larger than the memory required by an equivalent sequential program, particularly for programs that use recursion extensively. Since most parallel programs are nondeterministic in behavior, even when computing a deterministic result, parallel memory requirements may vary from run to run, even with the same data. Hence, parallel memory requirements may be both large (relative to memory requirements of an equivalent sequential program) and unpredictable. Assume that each parallel program has an underlying sequential execution order that may be used as a basis for predicting parallel memory requirements. We propose a simple restriction that is sufficient to ensure that any program that will run in n units of memory sequentially can run in mn units of memory on m processors, using a scheduling algorithm that is always within a factor of two of being optimal with respect to time. Any program can be transformed into one that satisfies the restriction, but some potential parallelism may be lost in the transformation. Alternatively, it is possible to define a parallel programming language in which only programs satisfying the restriction can be written     

On the power of algebraic branching programs of width two

We show that there are families of polynomials having small depth-two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clarifies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several settings.     

On the size of randomized OBDDs and read-once branching programs for k-stable functions

In this paper, a simple technique which unifies the known approaches for proving lower bound results on the size of deterministic, nondeterministic, and randomized OBDDs and kOBDDs is described.?As an application of this technique, a generic lower bound on the size of randomized OBDDs with bounded error is established for a class of functions which has been studied in the literature on branching programs for a long time. These functions have been called “k-stable” by Jukna. It follows that several standard functions are not contained in the analog of the class BPP for OBDDs. Furthermore, exponential lower bounds on the size of randomized kOBDDs are presented.?It is well known that k-stable functions with large k are hard for deterministic read-once branching programs. This is no longer true in the randomized case. It is shown here that a certain k-stable function due to Jukna, Razborov, Savicky, and Wegener has randomized branching programs of polynomial size, even with zero error. It follows that for the analogs of these classes defined in terms of the size of read-once branching programs. Received: September 3, 1998.     

Best case lower bounds for Heapsort

The performance of Heapsort algorithms on arbitrary input is examined. It is proved that ann logn?O(n) lower bound on the number of comparisons holds for a set of Heapsort algorithms, including Williams-Floyd's algorithm, Carlsson's bottom-up linear or binary insertion algorithm, and all up-down algorithms, on any input.     

Top-down lower bounds for depth-three circuits

We present a top-down lower bound method for depth-three , , ¬-circuits which is simpler than the previous methods and in some cases gives better lower bounds. In particular, we prove that depth-three , , ¬-circuits that compute parity (or majority) require size at least , respectively). This is the first simple proof of a strong lower bound by a top-down argument for non-monotone circuits.     

Distortion lower bounds for line embeddings

In this paper, we show how we can derive lower bounds and also compute the exact distortion for the line embeddings of some special metrics, especially trees and graphs with certain structure. Using linear programming to formulate a simpler version of the problem gives an interesting intuition and direction concerning the computation of general lower bounds for distortion into the line. We also show that our lower bounds on special cases of metrics are a lot better than previous lower bounds.     

Lifting lower bounds for tree-like proofs

It is known that constant-depth Frege proofs of some tautologies require exponential size. No such lower bound result is known for more general proof systems. We consider tree-like sequent calculus proofs in which formulas can contain modular connectives and only the cut formulas are restricted to be of constant depth. Under a plausible hardness assumption concerning small-depth Boolean circuits, we prove exponential lower bounds for such proofs. We prove these lower bounds directly from the computational hardness assumption. We start with a lower bound for cut-free proofs and “lift” it so it applies to proofs with constant-depth cuts. By using the same approach, we obtain the following additional results. We provide a much simpler proof of a known unconditional lower bound in the case where modular connectives are not used. We establish a conditional exponential separation between the power of constant-depth proofs that use different modular connectives. We show that these tree-like proofs with constant-depth cuts cannot polynomially simulate similar dag-like proofs, even when the dag-like proofs are cut-free. We present a new proof of the non-finite axiomatizability of the theory of bounded arithmetic I Δ₀(R). Finally, under a plausible hardness assumption concerning the polynomial-time hierarchy, we show that the hierarchy \({G_i^*}\) of quantified propositional proof systems does not collapse.     

Calculating lower bounds for caching problems

We present a general method for computing lower bounds for various caching problems. We apply the method to two well known problems, companion caching and weighted caching. For weighted caching, we increase the interval of weights where FIFO is known to be optimal. For companion caching, we give much simpler proofs for several known results, and give a new bound for the case of three types without reorganization or bypassing. Research supported by the Alexander von Humboldt Foundation.     

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.     

On lower bounds of the closeness between complexity classes

We show that if an NP-m-hard set is the union of a set in P_btt(Sparse) and the setA, then NP P_dtt(A). Since co-NP, R, and FewP are closed under _dtt ^P -reductions, so no NP-m-hard set is the union of a set in P_btt(Sparse) and a set in co-NP (resp. R, FewP) unless NP = co-NP (resp. NP = R, NP = FewP). We also study the distance between many important complexity classes. LetA,B be two sets. The distance function dist _A,B is defined as in [S1] such that dist _A,B (n) is the number of strings of length n inA B = (A – B) (B – A). We show that there exists a setA in p_{(k + 1)–tt}(Sparse) such that, for everyB in P _k–tt(Sparse), dist _A,B has an exponential lower bound.This research was supported in part by HTP 863.     

Branching programs provide lower bounds on the areas of multilective deterministic and nondeterministic VLSI-circuits

Each (nondeterministic) multilective VLSI-circuit C of area A can be simulated by an oblivious (disjunctive) branching program of width exp(O(A)) which has the same multiplicity of reading as C. That is why exponential lower bounds on the width of (disjunctive) oblivious branching programs of linear depth provide lower bounds of order Ω(n^1–2α), , on the area of (nondeterministic) multilective VLSI-circuits computing explicitly defined one-output Boolean functions, if the multiplicity of reading is bounded by O(log^αn). Lower bounds are derived for the sequence equality problem (SEQ) and the graph accessibility problem (GAP).     

New lower bounds for statistical query learning

We prove two lower bounds in the statistical query (SQ) learning model. The first lower bound is on weak-learning. We prove that for a concept class of SQ-dimension d, a running time of is needed. The SQ-dimension of a concept class is defined to be the maximum number of concepts that are “uniformly correlated”, in that each of their pair has nearly the same correlation. This lower bound matches the upper bound in Blum et al. (Weakly Learning DNF and Characterizing Statistical Query Learning using Fourier Analysis, STOC 1994, pp. 253-262), up to a logarithmic factor. We prove this lower bound against an “honest SQ-oracle”, which gives a stronger result than the ones against the more frequently used “adversarial SQ-oracles”. The second lower bound is more general. It gives a continuous trade-off between the “advantage” of an algorithm in learning the target function and the number of queries it needs to make, where the advantage of an algorithm is the probability it succeeds in predicting a label minus the probability it does not. Both lower bounds extend and/or strengthen previous results, and solve an open problem left in previous papers. An earlier version of this paper [K. Yang, New lower bounds for statistical query learning, in: The Proceedings of the 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, Lecture Notes in Computer Science, vol. 2375, 2002, pp. 229-243.] appeared in the proceedings of the 15th Annual Conference on Computational Learning Theory (COLT 2002).     

Exponential lower bounds for the pigeonhole principle

In this paper we prove an exponential lower bound on the size of bounded-depth Frege proofs for the pigeonhole principle (PHP). We also obtain an (loglogn)-depth lower bound for any polynomial-sized Frege proof of the pigeonhole principle. Our theorem nearly completes the search for the exact complexity of the PHP, as S. Buss has constructed polynomial-size, logn-depth Frege proofs for the PHP. The main lemma in our proof can be viewed as a general Håstad-style Switching Lemma for restrictions that are partial matchings. Our lower bounds for the pigeonhole principle improve on previous superpolynomial lower bounds.     

Combinatorial lower bounds for secret sharing schemes

In a perfect secret sharing scheme, it holds that , where S denotes the secret and denotes the set of the share of user i. On the other hand, it is well known that if S is not uniformly distributed, where denotes the set of secrets. In this case, . Then, which is bigger, or We first prove that for any distribution on S by using a combinatorial argument. This is a more sharp lower bound on for not uniformly distributed S. Our proof makes it intuitively clear why must be so large. Next, we extend our technique to show that max_i for some access structure.