Exponential Sums and Circuits with a Single Threshold Gate and Mod-Gates

Consider circuits consisting of a threshold gate at the top, Mod _m gates at the next level (for a fixed m ), and polylog fan-in AND gates at the lowest level. It is a difficult and important open problem to obtain exponential lower bounds for such circuits. Here we prove exponential lower bounds for restricted versions of this model, in which each Mod _m -of-AND subcircuit is a symmetric function of the inputs to that subcircuit. We show that if q is a prime not dividing m , the Mod _q function requires exponential-size circuits of this type. This generalizes recent results and techniques of Cai et al. [CGT] (which held only for q=2 ) and Goldmann (which held only for depth two threshold over Mod _m circuits). As a further generalization of the [CGT] result, the symmetry condition on the Mod _m subcircuits can be relaxed somewhat, still resulting in an exponential lower bound. The basis of the proof is to reduce the problem to estimating an exponential sum, which generalizes the notion of ``correlation" studied by [CGT]. This identifies the type of exponential sum that will be instrumental in proving the general case. Along the way we substantially simplify previous proofs. Received June 1997, and in final form October 1998.     

On the Correlation Between Parity and Modular Polynomials

We consider the problem of bounding the correlation between parity and modular polynomials over ℤ _q , for arbitrary odd integer q≥3. We prove exponentially small upper bounds for classes of polynomials with certain linear algebraic properties. As a corollary, we obtain exponential lower bounds on the size necessary to compute parity by depth-3 circuits with a MAJORITY gate at the top, MOD _q gates at the middle level and AND gates at the input level, when the polynomials corresponding to the depth-2 MOD _q ○AND subcircuits satisfy our conditions. Our methods also yield lower bounds for depth-3 MAJ○MOD _q ○MOD ₂ circuits (under certain restrictions) for computing parity. Our technique is based on a new general representation of the correlation using exponential sums, that allows to take advantage of the linear algebraic structure of the corresponding polynomials.     

The “log rank” conjecture for modular communication complexity

The “log rank” conjecture involves the question of how precisely the deterministic communication complexity of a problem can be described in terms of algebraic invariants of the communication matrix of this problem. We answer this question in the context of modular communication complexity. We show that the modular communication complexity can be exactly characterised in terms of the logarithm of a certain rigidity function of the communication matrix. Thus, we are able to exactly determine the modular communication complexity of several problems, such as, e.g., set disjointness, comparability, and undirected graph connectivity. From the bounds obtained for the modular communication complexity we deduce exponential lower bounds on the size of depth-two circuits having arbitrary symmetric gates at the bottom level and a MOD _m -gate at the top. Received: April 14, 2000.     

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.     

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.     

Circuits and multi-party protocols

Using multi-party communication techniques, we prove that depth-3 circuits with a threshold gate at the top, arbitrary symmetric gates at the next level, and fan-in k MOD _m gates at the bottom need exponential size to compute the k-wise inner product function of Babai, Nisan and Szegedy, where m is an odd positive integer satisfying . This is one of the rare lower-bound results involving MOD _m gates with non-prime power moduli.?Exponential gap theorems are also presented between the multi-party communication complexities of closely related functions. Received: January 5, 1994     

The Monotone Circuit Complexity of Quadratic Boolean Functions

Several results on the monotone circuit complexity and the conjunctive complexity, i.e., the minimal number of AND gates in monotone circuits, of quadratic Boolean functions are proved. We focus on the comparison between single level circuits, which have only one level of AND gates, and arbitrary monotone circuits, and show that there is an exponential gap between the conjunctive complexity of single level circuits and that of general monotone circuits for some explicit quadratic function. Nearly tight upper bounds on the largest gap between the single level conjunctive complexity and the general conjunctive complexity over all quadratic functions are also proved. Moreover, we describe the way of lower bounding the single level circuit complexity and give a set of quadratic functions whose monotone complexity is strictly smaller than its single level complexity.     

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.     

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.     

Computing Boolean functions by polynomials and threshold circuits

We investigate the computational power of threshold—AND circuits versus threshold—XOR circuits. In contrast to the observation that small weight threshold—AND circuits can be simulated by small weight threshold—XOR circuit, we present a function with small size unbounded weight threshold—AND circuits for which all threshold—XOR circuits have exponentially many nodes. This answers the basic question of separating subsets of the hypercube by hypersurfaces induced by sparse real polynomials. We prove our main result by a new lower bound argument for threshold circuits. Finally we show that unbounded weight threshold gates cannot simulate alternation: There are -functions which need exponential size threshold—AND circuits. Received: August 8, 1996.     

On the Incompressibility of Monotone DNFs

We prove optimal lower bounds for multilinear circuits and for monotone circuits with bounded depth. These lower bounds state that, in order to compute certain functions, these circuits need exactly as many OR gates as the respective DNFs. The proofs exploit a property of the functions that is based solely on prime implicant structure. Due to this feature, the lower bounds proved also hold for approximations of the considered functions that are similar to slice functions. Known lower bound arguments cannot handle these kinds of approximations. In order to show limitations of our approach, we prove that cliques of size n - 1 can be detected in a graph with n vertices by monotone formulas with O(log n) OR gates. Our lower bound for multilinear circuits improves a lower bound due to Borodin, Razborov and Smolensky for nondeterministic read-once branching programs computing the clique function.     

Learning a circuit by injecting values

We propose a new model for exact learning of acyclic circuits using experiments in which chosen values may be assigned to an arbitrary subset of wires internal to the circuit, but only the value of the circuit's single output wire may be observed. We give polynomial time algorithms to learn (1) arbitrary circuits with logarithmic depth and constant fan-in and (2) Boolean circuits of constant depth and unbounded fan-in over AND, OR, and NOT gates. Thus, both AC0 and NC1 circuits are learnable in polynomial time in this model. Negative results show that some restrictions on depth, fan-in and gate types are necessary: exponentially many experiments are required to learn AND/OR circuits of unbounded depth and fan-in; it is NP-hard to learn AND/OR circuits of unbounded depth and fan-in 2; and it is NP-hard to learn circuits of constant depth and unbounded fan-in over AND, OR, and threshold gates, even when the target circuit is known to contain at most one threshold gate and that threshold gate has threshold 2. We also consider the effect of adding an oracle for behavioral equivalence. In this case there are polynomial-time algorithms to learn arbitrary circuits of constant fan-in and unbounded depth and to learn Boolean circuits with arbitrary fan-in and unbounded depth over AND, OR, and NOT gates. A corollary is that these two classes are PAC-learnable if experiments are available. Finally, we consider an extension of the model called the synchronous model. We show that an even more general class of circuits are learnable in this model. In particular, we are able to learn circuits with cycles.     

An Exponential Lower Bound for the Size of Monotone Real Circuits

We prove a lower bound, exponential in the eighth root of the input length, on the size of monotone arithmetic circuits that solve an NP problem related to clique detection. The result is more general than the famous lower bound of Razborov and Andreev, because the gates of the circuit are allowed to compute arbitrary monotone binary real-valued functions (including AND and OR). Our proof is relatively simple and direct and uses the method of counting bottlenecks. The generalization was proved independently by Pudlák using a different method, who also showed that the result can be used to obtain an exponential lower bound on the size of unrestricted cutting plane proofs in the propositional calculus.     

Upper bounds for reversible circuits based on Young subgroups

We present tighter upper bounds on the number of Toffoli gates needed in reversible circuits. Both multiple controlled Toffoli gates and mixed polarity Toffoli gates have been considered for this purpose. The calculation of the bounds is based on a synthesis approach based on Young subgroups that results in circuits using a more generalized gate library. Starting from an upper bound for this library we derive new bounds which improve the existing bound by around 77%.     

Some order dimension bounds for communication complexity problems

Summary We associate with a general (0, 1)-matrixM an ordered setP(M) and derive lower and upper bounds for the deterministic communication complexity ofM in terms of the order dimension ofP(M). We furthermore consider the special class of communication matricesM obtained as cliques vs. stable sets incidence matrices of comparability graphsG. We bound their complexity byO((logd)·(logn)), wheren is the number of nodes ofG andd is the order dimension of an orientation ofG. In this special case, our bound is shown to improve other well-known bounds obtained for the general cliques vs. stable set problem.     

Randomized Priority Queues for Fast Parallel Access

We present simple randomized algorithms for parallel priority queues on distributed memory machines. Inserting O(n) elements or deleting the O(n) out ofmsmallest elements usingnprocessors requires O(T_coll+ log(m/n)) amortized time with high probability whereT_collbounds the time for performing prefix sums and randomized routing. The memory requirement is bounded by (m/n)(1 +o(1)) + O(logn) whp. These bounds are an improvement over the best previously known algorithms for many interconnection networks and even matches the speed of the best known PRAM algorithms. Generalizations for accessing thek⪢nsmallest elements are even more efficient. A portable implementation using MPI demonstrates that our approach is already useful for medium scale parallelism. Two parallel selection algorithms for randomly placed data are a spin-off. One runs in time O(T_coll) with high probability, beating a lower bound for the worst case. The other requires only a single reduction operation.     

On the message complexity of binary byzantine agreement under crash failures

Summary The binary Byzantine Agreement problem requiresn–1 receivers to agree on the binary value broadcast by a sender even when some of thesen processes may be faulty. We investigate the message complexity of protocols that solve this problem in the case of crash failures. In particular, we derive matching upper and lower bounds on the total, worst and average case number of meassages needed in the failure-free executions of such protocols.More specifically, we prove that any protocol that tolerates up tot faulty processes requires a total of at leastn+t–1 messages in its failure-free executions —and, therefore, at least [(n+t–1)/2] messages in the worst case and min (P ₀,P ₁)·(n+t–1) meassages in the average case, whereP _v is the probability that the value of the bit that the sender wants to broadcast isv. We also give protocols that solve the problem using only the minimum number of meassages for these three complexity measures. These protocols can be implemented by using 1-bit messages. Since a lower bound on the number of messages is also a lower bound on the number of meassage bits, this means that the above tight bounds on the number of messages are also tight bounds on the number of meassage bits. Vassos Hadzilacos received a BSE from Princeton University in 1980 and a PhD from Harvard University in 1984, both in Computer Science. In 1984 he joined the Department of Computer Science at the University of Toronto where he is currently an Associate Professor. In 1990–1991 he was visiting Associate Professor in the Department of Computer Science at Cornell University. His research interests are in the theory of distributed systems. Eugene Amdur obtained a B. Math from the University of Waterloo in 1986 and a M.Sc. from the University of Toronto in 1988. He is currently employed by the Vision and Robotics group at the University of Toronto in both technical and research capacities. His current areas of interest are vision, robotics, and networking. Samuel Weber received his B.Sc. in Mathematics and Computer Science and his M.Sc. in Computer Science from the University of Toronto. Currently, he is at Cornell University as a Ph.D. student in Computer Science with a minor in Psychology. His research interests include distributed systems, and the semantics of programming languages.     

On Spectral Bounds for the k-Partitioning of Graphs

When executing processes on parallel computer systems a major bottle-neck is interprocessor communication. One way to address this problem is to minimize the communication between processes that are mapped to different processors. This translates to the k-partitioning problem of the corresponding process graph, where k is the number of processors. The classical spectral lower bound of (|V|/2k)\sum ^k _i=1λ _i for the k-section width of a graph is well known. We show new relations between the structure and the eigenvalues of a graph and present a new method to get tighter lower bounds on the k-section width. This method makes use of the level structure defined by the k-section. We define a global expansion property and prove that for graphs with the same k-section width the spectral lower bound increases with this global expansion. We also present examples of graphs for which our new bounds are tight up to a constant factor.