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.     

Upper and lower bounds for some depth-3 circuit classes

We investigate the complexity of depth-3 threshold circuits with majority gates at the output, possibly negated AND gates at level two, and MOD _m gates at level one. We show that the fan-in of the AND gates can be reduced toO(logn) in the case wherem is unbounded, and to a constant in the case wherem is constant. We then use these upper bounds to derive exponential lower bounds for this class of circuits. In the unboundedm case, this yields a new proof of a lower bound of Grolmusz; in the constantm case, our result sharpens his lower bound. In addition, we prove an exponential lower bound if OR gates are also permitted on level two andm is a constant prime power.Dedicated to the memory of Roman Smolensky     

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.     

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

On the correlation of symmetric functions

Thecorrelation between two Boolean functions ofn inputs is defined as the number of times the functions agree minus the number of times they disagree, all divided by 2 ⁿ . In this paper we compute, in closed form, the correlation between any twosymmetric Boolean functions. As a consequence of our main result, we get that every symmetric Boolean function having an odd period has anexponentially small correlation (inn) with the parity function. This improves a result of Smolensky [12] restricted to symmetric Boolean functions: the correlation between parity and any circuit consisting of a Mod _q gate over AND gates of small fan-in, whereq is odd and the function computed by the sum of the AND gates is symmetric, is bounded by 2^−Ω(n). In addition, we find that for a large class of symmetric functions the correlation with parity isidentically zero for infinitely manyn. We characterize exactly those symmetric Boolean functions having this property. This research was supported in part by NSF Grant CCR-9057486. Jin-Yi Cai was supported in part by an Alfred T. Sloan Fellowship in computer science. The work of F. Green was done in part while visiting Princeton University, while the work of T. Thierauf was done in part while visiting Princeton University and the University of Rochester. The third author was supported in part by DFG Postdoctoral Stipend Th 472/1-1 and by NSF Grant CCR-8957604.     

Isolating an Odd Number of Elements and Applications in Complexity Theory

Naor and Naor [11] implicitly isolate an odd number of elements of a nonempty set of n -bit vectors. We perform a tighter analysis of their construction and obtain better probability bounds. Using this construction, we improve bounds on several results in complexity theory that originally used a construction due to Valiant and Vazirani [18]. In particular, we obtain better bounds on polynomials which approximate boolean functions; improve bounds on the running time of the ⊕ P machine in Toda's result [16]; and improve bounds on the size of threshold circuits accepting languages accepted by AC ⁰ circuits. Received July 1993, and in revised form January 1995, and in final form February 1997.     

Special sequences as subcodes of reed-solomon codes

We consider sequences in which every symbol of an alphabet occurs at most once. We construct families of such sequences as nonlinear subcodes of a q-ary [n, k, n − k + 1] _q Reed-Solomon code of length n ≤ q consisting of words that have no identical symbols. We introduce the notion of a bunch of words of a linear code. For dimensions k ≤ 3 we obtain constructive lower estimates (tight bounds in a number of cases) on the maximum cardinality of a subcode for various n and q, and construct subsets of words meeting these estimates and bounds. We define codes with words that have no identical symbols, observe their relation to permutation codes, and state an optimization problem for them.     

New One-Generator Quasi-cyclic Codes over GF(7)

Let [n,k,d] _q codes be linear codes of length n, dimension k, and minimum Hamming distance d over GF(q). In this paper, seventeen new codes are constructed, which improve the known lower bounds on minimum distance.     

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.     

Majority gates vs. general weighted threshold gates

In this paper we study small depth circuits that contain threshold gates (with or without weights) and parity gates. All circuits we consider are of polynomial size. We prove several results which complete the work on characterizing possible inclusions between many classes defined by small depth circuits. These results are the following:

New upper and lower bounds for the eigenvalues of the Sturm-Liouville problem

We derive new inequalities for the eigenvaluesλ _k of the Sturm-Liouville problem?u″+qu=λu, u(0)=u(π)=0 under the usual hypothesis thatq has mean value zero. The estimates give upper and lower bounds of the form |λ _k ?k ²|≤p _1,m k ^?m +P _2,m k ^2m ,k ²≥3‖q‖ _m ,m=1, 2 where ‖q‖ _m is the norm ofq in a Sobolev spaceH ^m (0, π) and theP's are homogeneous polynomials of degree at most 3 in ‖q‖ _m . Such bounds are used in the analysis of the inverse Sturm-Liouville problem.     

New Quasi-cyclic Degenerate Linear Codes over GF(8)

Let [n, k, d] _q code be a linear code of length n, dimension k, and minimum Hamming distance d over GF(q). One of the most important problems in coding theory is to construct codes with best possible minimum distances. Recently, quasi-cyclic (QC) codes were proved to contain many such codes. In this paper, twenty-five new codes over GF(8) are constructed, which improve the best known lower bounds on minimum distance.     

On the power of small-depth threshold circuits

We investigate the power of threshold circuits of small depth. In particular, we give functions that require exponential size unweighted threshold circuits of depth 3 when we restrict the bottom fanin. We also prove that there are monotone functionsf _k that can be computed in depthk and linear size , -circuits but require exponential size to compute by a depthk–1 monotone weighted threshold circuit.     

Evaluating spectral norms for constant depth circuits with symmetric gates

The Fourier spectrum and its norms are given as explicit arithmetic expressions and evaluated, for Boolean functions computed by classes of constant depth, read-once circuits consisting of an arbitrary set of symmetric gates. Previous results of this nature estimate the spectralL ₁ norm of functions computed by certain types of decision trees [20], [7], and in some cases, give randomizedprocedures that evaluate the spectrum by clever rounding [20]. One corollary of our results provides a large class ofAC ⁰ functions whose spectralL ₁ norm is exponential, thus generalizing the single example of such a function given in [9]. This shows that almost every read-onceAC ⁰ function does not belong in the classPL ₁ of functions with polynomially bounded spectral norms.Implications of our results and technique are discussed, for estimating the spectral norms ofany function in a constant depth circuit class, using the coding theoretic concept of weight distributions. Evaluating the spectral norms for any such function reduces to estimating certain non-trivial weight distributions of simple, linear codes.     

Limit laws for terminal nodes in random circuits with restricted fan-out: a family of graphs generalizing binary search trees

We introduce a family of graphs C(n,i,s,a) that generalizes the binary search tree. The graphs represent logic circuits with fan-in i, restricted fan-out s, and arising by n progressive additions of random gates to a starting circuit of a isolated nodes. We show via martingales that a suitably normalized version of the number of terminal nodes in binary circuits converges in distribution to a normal random variate.Received: 23 July 2003, Published online: 29 October 2004     

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.     

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.