On the computational power of probabilistic and quantum branching program

In this paper, we show that one-qubit polynomial time computations are as powerful as NC¹ circuits. More generally, we define syntactic models for quantum and stochastic branching programs of bounded width and prove upper and lower bounds on their power. We show that any NC¹ language can be accepted exactly by a width-2 quantum branching program of polynomial length, in contrast to the classical case where width 5 is necessary unless NC¹ = ACC. This separates width-2 quantum programs from width-2 doubly stochastic programs as we show the latter cannot compute the middle bit of multiplication. Finally, we show that bounded-width quantum and stochastic programs can be simulated by classical programs of larger but bounded width, and thus are in NC¹. For read-once quantum branching programs (QBPs), we give a symmetric Boolean function which is computable by a read-once QBP with O (log n) width, but not by a deterministic read-once BP with o (n) width, or by a classical randomized read-once BP with o (n) width which is “stable” in the sense that its transitions depend on the value of the queried variable but do not vary from step to step. Finally, we present a general lower bound on the width of read-once QBPs, showing that our O (log n) upper bound for this symmetric function is almost tight.     

On lower bounds for read-k-times branching programs

A syntactic read-k-times branching program has the restriction that no variable occurs more thank times on any path (whether or not consistent) of the branching program. We first extend the result in [31], to show that the “n/2 clique only function”, which is easily seen to be computable by deterministic polynomial size read-twice programs, cannot be computed by nondeterministic polynomial size read-once programs, although its complement can be so computed. We then exhibit an explicit Boolean functionf such that every nondeterministic syntactic read-k-times branching program for computingf has size exp $$\left( {\Omega \left( {\frac{n}{{4^k k^3 }}} \right)} \right).$$      

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.     

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].     

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 hierarchy result for read-once branching programs with restricted parity nondeterminism

Restricted branching programs are considered in complexity theory in order to study the space complexity of sequential computations and in applications as a data structure for Boolean functions. In this paper (,k)-branching programs and (,k)-branching programs are considered, i.e., branching programs starting with a - (or -)node with a fan-out of k whose successors are k read-once branching programs. This model is motivated by the investigation of the power of nondeterminism in branching programs and of similar variants that have been considered as a data structure. Lower bound methods and hierarchy results for polynomial size (,k)- and (,k)-branching programs with respect to k are presented.     

Exponential lower bounds for depth three Boolean circuits

We consider the class of unbounded fan-in depth three Boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR. It is known that the smallest such circuit computing the parity function has gates (for k = O(n ^1/2)) for some , and this was the best lower bound known for explicit (P-time computable) functions. In this paper, for k = 2, we exhibit functions in uniform NC ¹ that require size depth 3 circuits. The main tool is a theorem that shows that any circuit on n variables that accepts a inputs and has size s must be constant on a projection (subset defined by equations of the form x _i = 0, x _i = 1, x _i = x _j or x _i = ) of dimension at least log(a/s)log n. Received: April 1, 1997.     

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).     

Graph Complexity and Slice Functions

   Abstract. A graph-theoretic approach to study the complexity of Boolean functions was initiated by Pudlák, R?dl, and Savicky [PRS] by defining models of computation on graphs. These models generalize well-known models of Boolean complexity such as circuits, branching programs, and two-party communication complexity. A Boolean function f is called a 2-slice function if it evaluates to zero on inputs with less than two 1's and evaluates to one on inputs with more than two 1's. On inputs with exactly two 1's f may be nontrivially defined. There is a natural correspondence between 2-slice functions and graphs. Using the framework of graph complexity, we show that sufficiently strong superlinear monotone lower bounds for the very special class of {2-slice functions} would imply superpolynomial lower bounds over a complete basis for certain functions derived from them. We prove, for instance, that a lower bound of n ^1+Ω(1) on the (monotone) formula size of an explicit 2-slice function f on n variables would imply a 2 ^Ω(ℓ) lower bound on the formula size over a complete basis of another explicit function g on l variables, where l=Θ( log n) . We also consider lower bound questions for depth-3 bipartite graph complexity. We prove a weak lower bound on this measure using algebraic methods. For instance, our result gives a lower bound of Ω(( log n) ³ / ( log log n) ⁵ ) for bipartite graphs arising from Hadamard matrices, such as the Paley-type bipartite graphs. Lower bounds for depth-3 bipartite graph complexity are motivated by two significant applications: (i) a lower bound of n ^Ω(1) on the depth-3 complexity of an explicit n -vertex bipartite graph would yield superlinear size lower bounds on log-depth Boolean circuits for an explicit function, and (ii) a lower bound of

Functions that have read-once branching programs of quadratic size are not necessarily testable

A property of binary strings is constructed that has a representation by a collection of read-once branching programs of quadratic size but which is not ε-testable for some fixed ε>0. This shows that Newman's result [Proc. 41st FOCS, 2000, pp. 251-258] cannot be generalized to functions representable by read-once branching programs of polynomial size.     

Graph Complexity and Slice Functions

Abstract. A graph-theoretic approach to study the complexity of Boolean functions was initiated by Pudlák, Rödl, and Savický [PRS] by defining models of computation on graphs. These models generalize well-known models of Boolean complexity such as circuits, branching programs, and two-party communication complexity. A Boolean function f is called a 2-slice function if it evaluates to zero on inputs with less than two 1's and evaluates to one on inputs with more than two 1's. On inputs with exactly two 1's f may be nontrivially defined. There is a natural correspondence between 2-slice functions and graphs. Using the framework of graph complexity, we show that sufficiently strong superlinear monotone lower bounds for the very special class of {2-slice functions} would imply superpolynomial lower bounds over a complete basis for certain functions derived from them. We prove, for instance, that a lower bound of n ^1+Ω(1) on the (monotone) formula size of an explicit 2-slice function f on n variables would imply a 2 ^Ω(?) lower bound on the formula size over a complete basis of another explicit function g on l variables, where l=Θ( log n) . We also consider lower bound questions for depth-3 bipartite graph complexity. We prove a weak lower bound on this measure using algebraic methods. For instance, our result gives a lower bound of Ω(( log n) ³ / ( log log n) ⁵ ) for bipartite graphs arising from Hadamard matrices, such as the Paley-type bipartite graphs. Lower bounds for depth-3 bipartite graph complexity are motivated by two significant applications: (i) a lower bound of n ^Ω(1) on the depth-3 complexity of an explicit n -vertex bipartite graph would yield superlinear size lower bounds on log-depth Boolean circuits for an explicit function, and (ii) a lower bound of $\exp((\log \log n)^{\omega(1)})$ would give an explicit language outside the class Σ ₂ ^cc of the two-party communication complexity as defined by Babai, Frankl, and Simon [BFS]. Our lower bound proof is based on sign-representing polynomials for DNFs and lower bounds on ranks of ±1 matrices even after being subjected to sign-preserving changes to their entries. For the former, we use a result of Nisan and Szegedy [NS] and an idea from a recent result of Klivans and Servedio [KS]. For the latter, we use a recent remarkable lower bound due to Forster [F1].     

An Improved Hierarchy Result for Partitioned BDDs

One of the great challenges of complexity theory is the problem of analyzing the dependence of the complexity of Boolean functions on the resources nondeterminism and randomness. So far this problem could be solved only for very few models of computation. For so-called partitioned binary decision diagrams , which are a restricted variant of nondeterministic read-once branching programs, Bollig and Wegener have proven an astonishing hierarchy result which shows that the smallest possible decrease of the available amount of nondeterminism may incur an exponential blow-up of the branching program size. They have shown that k -partitioned BDDs which may nondeterministically choose between k alternative subprograms may be exponentially larger than (k+1) -partitioned BDDs for the same function if k = o(( log n / log log n) ^1/2 ) , where n is the input size. In this paper an improved hierarchy result is established which still works if the number of nondeterministic decisions is O((n/ log ^1+ε n) ^1/4 ) , where ε > 0 is an arbitrary small constant. Received November 25, 1999.     

Lower Bounds on the Randomized Communication Complexity of Read-Once Functions

We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae. A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond to variables, and the internal nodes are labeled by binary connectives. Under certain assumptions, this representation is unique. Thus, one can define the depth of a formula as the depth of the tree that represents it. The complexity of the evaluation of general read-once formulae has attracted interest mainly in the decision tree model. In the communication complexity model many interesting results deal with specific read-once formulae, such as DISJOINTNESS and TRIBES. In this paper we use information theory methods to prove lower bounds that hold for any read-once formula. Our lower bounds are of the form n(f)/c^d(f), where n(f) is the number of variables and d(f) is the depth of the formula, and they are optimal up to the constant in the base of the denominator.     

Pseudorandom generators and learning algorithms forAC 0

For anyAC ⁰ functionf ofn bits, there is a polynomialp such that anyp(logn)-wise decomposable distribution foolsf. In other words,f cannot distinguish between the pseudorandom strings in the distribution and truly random strings. The polynomialp depends only on the size and depth of the circuit computingf.This subsumes and extends the class of distributions that were previously known to foolAC ⁰ functions, and partially answers an open question posed by Linial and Nisan in 1990, as to whether every polylog-wise independent distribution foolsAC ⁰ functions or not.Each polylog-wise decomposable distribution serves as a fixed training set of examples for learning (approximately interpolating) allAC ⁰ functions computed by circuits of some fixed depth and size. Furthermore, small, natural distributions (training sets) exist that yield deterministic learning algorithms that run in timeO (2^polylogn ) forAC ⁰ functions, where the degree of the polylog depends on the size and depth of the circuit to be learnt.This improves on the randomized algorithms with the same time complexity given, for example, by Linialet al. in 1989, where the examples for the training set are picked randomly from specific distributions.     

Connections among nonlinearity,avalanche and correlation immunity

Nonlinear Boolean functions play an important role in the design of block ciphers, stream ciphers and one-way hash functions. Over the years researchers have identified a number of indicators that forecast nonlinear properties of these functions. Studying the relationships among these indicators has been an area that has received extensive research. The focus of this paper is on the interplay of three notable nonlinear indicators, namely nonlinearity, avalanche and correlation immunity. We establish, for the first time, an explicit and simple lower bound on the nonlinearity N_f of a Boolean function f of n variables satisfying the avalanche criterion of degree p, namely, N_f⩾2ⁿ⁻¹−2^{n−1−(1/2)p}. We also identify all the functions whose nonlinearity attains the lower bound. As a further contribution of this paper, we prove that except for very few cases, the sum of the degree of avalanche and the order of correlation immunity of a Boolean function of n variables is at most n−2. The new results obtained in this work further highlight the significance of the fact that while avalanche property is in harmony with nonlinearity, both go against correlation immunity.     

The Complexity of Boolean Functions in Different Characteristics

Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree modulo p must have high complexity in every other characteristic q. More precisely, we show the following results about Boolean functions f : {0, 1}ⁿ → {0, 1} which depend on all n variables, and distinct primes p, q:

On the Sample Complexity of Weak Learning

In this paper, we study the sample complexity of weak learning. That is, we ask how many data must be collected from an unknown distribution in order to extract a small but significant advantage in prediction. We show that it is important to distinguish between those learning algorithms that output deterministic hypotheses and those that output randomized hypotheses. We prove that in the weak learning model, any algorithm using deterministic hypotheses to weakly learn a class of Vapnik-Chervonenkis dimension d(n) requires Ω ([formula]) examples. In contrast, when randomized hypotheses are allowed, we show that Θ (1) examples suffice in some cases. We then show that there exists an efficient algorithm using deterministic hypotheses that weakly learns against any distribution on a set of size d(n) with only O(d(n)^2/3) examples. Thus for the class of symmetric Boolean functions over n variables, where the strong learning sample complexity is Θ (n), the sample complexity for weak learning using deterministic hypotheses is Ω ([formula]) and O(n^2/3), and the sample complexity for weak learning using randomized hypotheses is Θ (1). Next we prove the existence of classes for which the distribution-free sample size required to obtain a slight advantage in prediction over random guessing is essentially equal to that required to obtain arbitrary accuracy. Finally, for a class of small circuits, namely all parity functions of subsets of n Boolean variables, we prove a weak learning sample complexity of Θ(n). This bound holds even if the weak learning algorithm is allowed to replace random sampling with membership queries, and the target distribution is uniform on {0, 1}ⁿ.     

The Power of Nondeterminism and Randomness for Oblivious Branching Programs

Abstract. This paper abstracts and generalizes the known approaches for proving lower bounds on the size of various variants of oblivious branching programs (oblivious BPs for short), providing an easy-to-use technique which works for all nondeterministic and randomized modes of acceptance. The technique is applied to obtain the following results concerning the power of nondeterminism and randomness for oblivious BPs: <p>— Oblivious read-once BPs, better known as OBDDs (ordered binary decision diagrams), are used in many applications and their structure is well understood in the deterministic case. It has been open so far to compare the power of nondeterministic OBDDs with so-called partitioned BDDs which are a variant of nondeterministic branching programs also used in practice. A k -partitioned BDD has a nondeterministic node at the top by which one out of k deterministic OBDDs with possibly different variable orders is chosen. It is proven here that the two models are incomparable as long as k is bounded by a logarithmic function in the input length. <p>— It is shown that deterministic oblivious read-k -times BPs for an explicitly defined function require superpolynomial size, for k logarithmic in the input length, while there are Las Vegas oblivious read-twice BPs of linear size for this function. This is in contrast to the situation for OBDDs, for which the respective size measures are polynomially related. <p>— Furthermore, an explicitly defined function is presented for which randomized oblivious read-k -times BPs with bounded error require exponential size, while the function as well as its complement can be represented in polynomial size by nondeterministic oblivious read-k -times BPs and deterministic oblivious read-(k+1) -times BPs, where k=o(log n) .     

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.