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 the polynomial calculus

We show that polynomial calculus proofs (sometimes also called Groebner proofs) of the pigeonhole principle must have degree at least over any field. This is the first non-trivial lower bound on the degree of polynomial calculus proofs obtained without using unproved complexity assumptions. We also show that for some modifications of , expressible by polynomials of at most logarithmic degree, our bound can be improved to linear in the number of variables. Finally, we show that for any Boolean function in n variables, every polynomial calculus proof of the statement “ cannot be computed by any circuit of size t,” must have degree . Loosely speaking, this means that low degree polynomial calculus proofs do not prove . Received: January 15, 1997.     

On P versus NP $ \cap $ co-NP for decision trees and read-once branching programs

It is known that if a Boolean function f in n variables has a DNF and a CNF of size then f also has a (deterministic) decision tree of size exp(O(log n log² N)). We show that this simulation cannot be made polynomial: we exhibit explicit Boolean functions f that require deterministic trees of size exp where N is the total number of monomials in minimal DNFs for f and ?f. Moreover, we exhibit new examples of explicit Boolean functions that require deterministic read-once branching programs of exponential size whereas both the functions and their negations have small nondeterministic read-once branching programs. One example results from the Bruen—Blokhuis bound on the size of nontrivial blocking sets in projective planes: it is remarkably simple and combinatorially clear. Other examples have the additional property that f is in AC⁰. Received: June 5 1997.     

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.     

Randomized vs. deterministic decision tree complexity for read-once Boolean functions

We consider the deterministic and the randomized decision tree complexities for Boolean functions, denotedDC(f) andRC(f), respectively. A major open problem is how smallRC(f) can be with respect toDC(f). It is well known thatRC(f)DC(f) ^0.5 for every Boolean functionf (called 0.5-exponent). On the other hand, some Boolean functionf is known to haveRC(f) = (DC(f))^0.753...) (or 0.753...-exponent). It is not known whether there is a Boolean function with exponent smaller than 0.753... Likewise, no lower bound for arbitrary Boolean functions with exponent greater than 0.5 is known.Our result is a 0.51 lower bound on the exponent for everyread-once function. Read-once means that each input variable appears exactly once in the Boolean formula representing the function. To obtain this result we generalize an existing lower bound technique and combine it with restriction arguments. This result provides a lower bound ofn ^0.51 on the number of positions that have to be evaluated by any randomized - pruning algorithm computing the value of any two-person zero-sum game tree withn final positions.     

A New Characterization of ACC0 and Probabilistic CC0

Barrington, Straubing & Thérien (1990) conjectured that the Boolean And function can not be computed by polynomial size constant depth circuits built from modular counting gates, i.e., by CC⁰ circuits. In this work we show that the And function can be computed by uniform probabilistic CC⁰ circuits that use only O(log n) random bits. This may be viewed as evidence contrary to the conjecture.     

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:

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.     

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.     

Representing Boolean functions as polynomials modulo composite numbers

Define the MOD _m -degree of a boolean functionF to be the smallest degree of any polynomialP, over the ring of integers modulom, such that for all 0–1 assignments , iff . We obtain the unexpected result that the MOD _m -degree of the OR ofN variables is , wherer is the number of distinct prime factors ofm. This is optimal in the case of representation by symmetric polynomials. The MOD _n function is 0 if the number of input ones is a multiple ofn and is one otherwise. We show that the MOD _m -degree of both the MOD _n and functions isN ⁽¹⁾ exactly when there is a prime dividingn but notm. The MOD _m -degree of the MOD _m function is 1; we show that the MOD _m -degree of isN ⁽¹⁾ ifm is not a power of a prime,O(1) otherwise. A corollary is that there exists an oracle relative to which the MOD _m P classes (such as P) have this structure: MOD _m P is closed under complementation and union iffm is a prime power, and MOD _n P is a subset of MOD _m P iff all primes dividingn also dividem.     

Limiting negations in non-deterministic circuits

The minimum number of NOT gates in a Boolean circuit computing a Boolean function f is called the inversion complexity of f. In 1958, Markov determined the inversion complexity of every Boolean function and, in particular, proved that log₂(n+1) NOT gates are sufficient to compute any Boolean function on n variables. In this paper, we consider circuits computing non-deterministically and determine the inversion complexity of every Boolean function. In particular, we prove that one NOT gate is sufficient to compute any Boolean function in non-deterministic circuits if we can use an arbitrary number of guess inputs.     

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.     

5元饱和最优布尔函数的计数问题

同时达到代数次数上界n-m-1和非线性度上界2^n-1-2^m+1的n元m阶弹性布尔函数(m＞n/2-2)具有3个Walsh谱值:0,±2^m+2这样的函数被称为饱和最优函数(saturated best,简称SB).将利用(32,6)Reed-Muller码陪集重量的分布,从一种全新的构造角度出发,给出n=5的饱和最优函数的个数.     

PI k mass production and an optimal circuit for the Nečiporuk slice

Letf: {0,1} ⁿ {0,1} ^m be anm-output Boolean function inn variables.f is called ak-slice iff(x) equals the all-zero vector for allx with Hamming weight less thank andf(x) equals the all-one vector for allx with Hamming weight more thank. Wegener showed that PI _k -set circuits (set circuits over prime implicants of lengthk) are at the heart of any optimum Boolean circuit for ak-slicef. We prove that, in PI _k -set circuits, savings are possible for the mass production of anyFX, i.e., any collectionF ofm output-sets given any collectionX ofn input-sets, if their PI _k -set complexity satisfiesSC _m (FX)3n+2m. This PI _k mass production, which can be used in monotone circuits for slice functions, is then exploited in different ways to obtain a monotone circuit of complexity 3n+o(n) for the Neiporuk slice, thus disproving a conjecture by Wegener that this slice has monotone complexity (n ^3/2). Finally, the new circuit for the Neiporuk slice is proven to be asymptotically optimal, not only with respect to monotone complexity, but also with respect to combinational complexity.     

On the degree of boolean functions as real polynomials

Every Boolean function may be represented as a real polynomial. In this paper, we characterize the degree of this polynomial in terms of certain combinatorial properties of the Boolean function. Our first result is a tight lower bound of Ω(logn) on the degree needed to represent any Boolean function that depends onn variables. Our second result states that for every Boolean functionf, the following measures are all polynomially related:

o The decision tree complexity off.

o The degree of the polynomial representingf.

o The smallest degree of a polynomialapproximating f in theL _max norm.

     

Exact Algorithms for MAX-SAT

The maximum satisfiability problem (MAX-SAT) is stated as follows: Given a boolean formula in CNF, find a truth assignment that satisfies the maximum possible number of its clauses. MAX-SAT is MAX-SNP-complete and received much attention recently. One of the challenges posed by Alber, Gramm and Niedermeier in a recent survey paper asks: Can MAX-SAT be solved in less than 2ⁿ “steps”? Here, n is the number of distinct variables in the formula and a step may take polynomial time of the input. We answered this challenge positively by showing that a popular algorithm based on branch-and-bound is bounded by O(2ⁿ) in time, where n is the maximum number of occurrences of any variable in the input.When the input formula is in 2-CNF, that is, each clause has at most two literals, MAX-SAT becomes MAX-2-SAT and the decision version of MAX-2-SAT is still NP-complete. The best bound of the known algorithms for MAX-2-SAT is O(m2^m/5), where m is the number of clauses. We propose an efficient decision algorithm for MAX-2-SAT whose time complexity is bound by O(n2ⁿ). This result is substantially better than the previously known results. Experimental results also show that our algorithm outperforms any algorithm we know on MAX-2-SAT.     

A class of boolean functions with linear combinational complexity

In this paper we investigate the combinational complexity of Boolean functions satisfying a certain property, ⁿ_k,m. A function of n variables has the ⁿ_k,m property if there are at least m functions obtainable from each way of restricting it to a subset of n - - k variables. We show that the complexity of a ⁿ_3,5 function is no less than , and this bound cannot be much improved. Further, we find that for each k, there are ⁿ_k,2^k functions with complexity linear in n.     

Harmonic Analysis, Real Approximation, and the Communication Complexity of Boolean Functions

The two-party communication complexity of Boolean function f is known to be at least log rank (M _f ), i.e., the logarithm of the rank of the communication matrix of f [19]. Lovász and Saks [17] asked whether the communication complexity of f can be bounded from above by (log rank (M _f )) ^c , for some constant c . The question was answered affirmatively for a special class of functions f in [17], and Nisan and Wigderson proved nice results related to this problem [20], but, for arbitrary f , it remained a difficult open problem. We prove here an analogous polylogarithmic upper bound in the stronger multiparty communication model of Chandra et al. [6], which, instead of the rank of the communication matrix, depends on the L ₁ norm of function f , for arbitrary Boolean function f . Received August 24, 1996; revised October 15, 1997.