Complex polynomials and circuit lower bounds for modular counting

We study the power of constant-depth circuits containing negation gates, unbounded fan-in AND and OR gates, and a small number of MAJORITY gates. It is easy to show that a depth 2 circuit of sizeO(n) (wheren is the number of inputs) containingO(n) MAJORITY gates can determine whether the sum of the input bits is divisible byk, for any fixedk>1, whereas it is known that this requires exponentialsize circuits if we have no MAJORITY gates. Our main result is that a constant-depth circuit of size containingn ^o(1) MAJORITY gates cannot determine if the sum of the input bits is divisible byk; moreover, such a circuit must give the wrong answer on a constant fraction of the inputs. This result was previously known only fork=2. We prove this by obtaining an approximate representation of the behavior of constant-depth circuits by multivariate complex polynomials.     

Lower bounds for modular counting by circuits with modular gates

We prove that constant depth circuits, with one layer of M O D _m gates at the inputs, followed by a fixed number of layers of M O D _p gates, where p is prime, require exponential size to compute the M O D _q function, if q is a prime that divides neither p nor m. Received: January 23, 1998.     

A lower bound method for quantum circuits

Quantum circuits, which are shallow, limited in the number of gates and additional workspace qubits, are popular for quantum computation because they form the simplest possible model similar to the classical model of a network of Boolean gates and capable of performing non-trivial computation. We give a new lower bound technique for such circuits and use it to give another proof that deterministic computation of the parity function cannot be performed by such circuits.     

A complex-number Fourier technique for lower bounds on the Mod-m degree

We say an integer polynomial p, on Boolean inputs, weakly m-represents a Boolean function f if p is nonconstant and is zero (mod m), whenever f is zero. In this paper we prove that if a polynomial weakly m-represents the Mod _q function on n inputs, where q and m are relatively prime and m is otherwise arbitrary, then the degree of the polynomial is . This generalizes previous results of Barrington, Beigel and Rudich, and Tsai, which held only for constant or slowly growing m. In addition, the proof technique given here is quite different. We use a method (adapted from Barrington and Straubing) in which the inputs are represented as complex q-th roots of unity. In this representation it is possible to compute the Fourier transform using some elementary properties of the algebraic integers. As a corollary of the main theorem and the proof of Toda's theorem, if q, p are distinct primes, any depth-three circuit that computes the Mod _q function, and consists of an exact threshold gate at the output, Mod _p gates at the next level, and AND gates of polylog fan-in at the inputs, must be of exponential size. We also consider the question of how well circuits consisting of one exact gate over ACC(p)-type circuits (where p is an odd prime) can approximate parity. It is shown that such circuits must have exponential size in order to agree with parity for more than 1/2 + o(1) of the inputs. Received: February 21, 1996.     

A lower bound for testing juntas

We show an Ω(m) lower bound on the number of queries required to test whether a Boolean function depends on at most m out of its n variables. This improves a previously known lower bound for testing this property. Our proof is simple and uses only elementary techniques.     

Reflections on “Representations of sets of Boolean functions by commutative rings” by Roman Smolensky

The paper by Roman Smolensky is a nice example of the art of studying mathematical structures that are, on the one hand, motivated by real computational problems but are, on the other hand, not obviously related.Dedicated to the memory of Roman Smolensky     

Communication complexity towards lower bounds on circuit depth

Karchmer, Raz, and Wigderson (1995) discuss the circuit depth complexity of n-bit Boolean functions constructed by composing up to d = log n/log log n levels of k = log n-bit Boolean functions. Any such function is in AC¹ . They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires depth. This would separate AC¹ from NC¹. They recommend using the communication game characterization of circuit depth. In order to develop techniques for using communication complexity to prove circuit depth lower bounds, they suggest an intermediate communication complexity problem which they call the Universal Composition Relation. We give an almost optimal lower bound of dk—O(d ²(k log k)^1/2) for this problem. In addition, we present a proof, directly in terms of communication complexity, that there is a function on k bits requiring circuit depth. Although this fact can be easily established using a counting argument, we hope that the ideas in our proof will be incorporated more easily into subsequent arguments which use communication complexity to prove circuit depth bounds. Received: July 30, 1999.     

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.     

Bounds on the Fourier coefficients of the weighted sum function

We estimate Fourier coefficients of a Boolean function which has recently been introduced in the study of read-once branching programs. Our bound implies that this function has rather “flat” Fourier spectrum and thus implies several lower bounds on some of its complexity measures.     

布尔函数线路复杂度的一个新的下界

布尔函数的线路复杂下界问题与Ｐ＝？ＮＰ问题有密切关系，若证明了ＮＰ中某问题的线路复杂度是非多项式的，则Ｐ≠ＮＰ。但证明了一个具体的布尔函数具有非线性的线路复杂度下界却是计算复杂性理论中最难的问题之一。迄今此问题的最好结果是由Ｎ．Ｂｌｕｍ于１８９４年给出的，他证明了一个布尔函数具有３ｎ－３的线路复杂度下界。本文针对同一个布尔函数，给出一个更好的下界３ｎ＋１。     

Symmetric approximation arguments for monotone lower bounds without sunflowers

We propose a symmetric version of Razborov's method of approximation to prove lower bounds for monotone circuit complexity. Traditionally, only DNF formulas have been used as approximators, whereas we use both CNF and DNF formulas. As a consequence we no longer need the Sun ower Lemma that has been essential for the method of approximation. The new approximation argument corresponds to Haken's recent method for proving lower bounds for monotone circuit complexity (counting bottlenecks) in a natural way.?We provide lower bounds for the BMS problem introduced by Haken, Andreev's polynomial problem, and for Clique. The exponential bounds obtained are the same as those previously best known for the respective problems. Received: July 16, 1996.     

Linear lower bounds on unbounded fan-in boolean circuits

A practical method for representing Turner Combinators is presented, which needs only O(n log n) space in the worst case for translating lambda expressions of length n. No precomputation is necessary in our translation, which should be contrasted with Burton's proposal. The runtime system can be implemented with virtually no essential change to Turner's reduction machine.     

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.     

Improved depth lower bounds for small distance connectivity

We consider the problem of determining, given a graph G with specified nodes s and t, whether or not there is a path of at most k edges in G from s to t. We show that solving this problem on polynomialsize unbounded fan-in circuits requires depth , improving on a depth lower bound of when given by Ajtai (1989), Bellantoni et al. (1992). More generally, we obtain an improved size-depth tradeoff lower bound for the problem for all .?The key to our technique is a new form of “switching lemma” which combines some of the features of iteratively shortening terms due to Furst et al. (1984) and Ajtai (1983) with the features of switching lemma arguments introduced by Yao (1985), H?stad (1987), and Cai (1986) that have been the methods of choice for subsequent results. Received: July 2, 1996.     

The size and depth of layered Boolean circuits

We consider the relationship between size and depth for layered Boolean circuits and synchronous circuits. We show that every layered Boolean circuit of size s can be simulated by a layered Boolean circuit of depth . For synchronous circuits of size s, we obtain simulations of depth . The best known result so far was by Paterson and Valiant (1976) [17], and Dymond and Tompa (1985) [6], which holds for general Boolean circuits and states that , where C(f) and D(f) are the minimum size and depth, respectively, of Boolean circuits computing f. The proof of our main result uses an adaptive strategy based on the two-person pebble game introduced by Dymond and Tompa (1985) [6]. Improving any of our results by polylog factors would immediately improve the bounds for general circuits.     

A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games

In this note we show that the asymmetric Prover-Delayer game developed in Beyersdorff et al. (2010) [2] for Parameterized Resolution is also applicable to other tree-like proof systems. In particular, we use this asymmetric Prover-Delayer game to show a lower bound of the form ²Ω(nlogn) for the pigeonhole principle in tree-like Resolution. This gives a new and simpler proof of the same lower bound established by Iwama and Miyazaki (1999) [7] and Dantchev and Riis (2001) [5].     

An exponential lower bound on the size of algebraic decision trees for Max

We prove an exponential lower bound on the size of any fixed degree algebraic decision tree for solving MAX, the problem of finding the maximum of n real numbers. This complements the n— 1 lower bound of [Rabin (1972)] on the depth of algebraic decision trees for this problem. The proof in fact gives an exponential lower bound on the size of the polyhedral decision problem MAX= for testing whether the j-th number is the maximum among a list of n real numbers. Previously, except for linear decision trees, no nontrivial lower bounds on the size of algebraic decision trees for any familiar problems are known. We also establish an interesting connection between our lower bound and the maximum number of minimal cutsets for any rank-d hypergraph on n vertices. Received: 15 April 1996     

A 4n-lower bound on the monotone network complexity of a one-output boolean function

The main purpose of Boolean network theory is to find functions f:{0, 1}ⁿ → {0, 1} with large network complexity. The best known lower bound over the complete basis of all binary functions is of size 3n for a non-monotone function (Blum (1982)). Bloniarz (1979) has proved a 3n-lower bound for the majority-function over the monotone basis. In this paper a special function is presented for which a lower bound of size 4n over the monotone basis can be proved.     

A 3-Party Simultaneous Protocol for SUM-INDEX

Abstract. We show that the SUM-INDEX function can be computed by a 3-party simultaneous protocol in which one player sends only O(n ^ɛ ) bits and the other sends O(n ^1-C(ɛ) ) bits (0<C(ɛ)<1 ). This implies that, in the Valiant—Nisan—Wigderson approach for proving circuit lower bounds, the SUM-INDEX function is not suitable as a target function.