Malign Distributions for Average Case Circuit Complexity

In contrast to machine models like Turing machines or random access machines, circuits are a static computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. Therefore, size and depth are natural and simple measures for circuits and provide a worst-case analysis. We consider a new model in which an internal gate is evaluated as soon as its result has been determined by a partial assignment of its inputs. This way, a dynamic notion of delay is obtained which gives rise to an average case measure for the time complexity of circuits. In a previous paper we have obtained tight upper and lower bounds for the average case complexity of several basic Boolean functions. This paper examines the asymptotic average case complexity for the set of alln-ary Boolean functions. In contrast to worst case analysis a simple counting argument does not work. We prove that with respect to the uniform probability distribution almost all Boolean functions require at leastn−log n−log log nexpected time. On the other hand, there is a significantly large subset of functions that can be computed with a constant average delay. Finally, for an arbitrary Boolean function we compare its worst case and average case complexity. It is shown that for each function that requires circuit depthd, i.e. of worst-case complexityd, the expected time complexity will be at leastd−log n−log dwith respect to an explicitly defined probability distribution. In addition, a nontrivial upper bound on the complexity of such a distribution will be obtained.     

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.     

Homogenization and the polynomial calculus

In standard implementations of the Gröbner basis algorithm, the original polynomials are homogenized so that each term in a given polynomial has the same degree. In this paper, we study the effect of homogenization on the proof complexity of refutations of polynomials derived from Boolean formulas in both the Polynomial Calculus (PC) and Nullstellensatz systems. We show that the PC refutations of homogenized formulas give crucial information about the complexity of the original formulas. The minimum PC refutation degree of homogenized formulas is equal to the Nullstellensatz refutation degree of the original formulas, whereas the size of the homogenized PC refutation is equal to the size of the PC refutation for the originals. Using this relationship, we prove nearly linear ((n/log n) vs. O(1)) separations between Nullstellensatz and PC degree, for a family of explicitly constructed contradictory 3CNF formulas. Previously, an (n ^1/2) separation had been proved for equations that did not correspond to any CNF formulas, and a log n separation for equations derived from kCNF formulas.     

Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape

We prove an O(t(n) ^d (t(n)) ^? / log t(n)) time bound for the sim-ulation of t(n) steps of a Turing machine using several one-dimensional work tapes on a Turing machine using one d-dimensional work tape, . We prove a matching lower bound which holds for the problem of recognizing languages on machines with a separate one-way input tape. Received: March 1995.     

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.     

The BNS-Chung criterion for multi-party communication complexity

The "Number on the Forehead" model of multi-party communication complexity was first suggested by Chandra, Furst and Lipton. The best known lower bound, for an explicit function (in this model), is a lower bound of , where n is the size of the input of each player, and k is the number of players (first proved by Babai, Nisan and Szegedy). This lower bound has many applications in complexity theory. Proving a better lower bound, for an explicit function, is a major open problem. Based on the result of BNS, Chung gave a sufficient criterion for a function to have large multi-party communication complexity (up to ). In this paper, we use some of the ideas of BNS and Chung, together with some new ideas, resulting in a new (easier and more modular) proof for the results of BNS and Chung. This gives a simpler way to prove lower bounds for the multi-party communication complexity of a function. Received: December 12, 1997.     

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

Verifying the determinant in parallel

In this paper, we investigate the complexity of verifying problems whose computation is equivalent to the determinant, both in the Boolean arithmetic circuit and in the Boolean circuit model. We observe that for a few problems, there exists an easy (NC ¹) verification algorithm. To characterize the harder ones, we define the class of problems that are reducible to the verification of the determinant, under two different reductions, and establish a list of complete problems in these classes. In particular, we prove that computing the rank is equivalent under AC ⁰ reductions to verifying the determinant. We show in the Boolean case that none of the complete problems can be recognized in NC ¹ unless L = NL. On the other hand, we show that for functions, there exists an NC ¹ checker even if they are hard to verify, and that they can be extended into functions whose verification is easy. received 24 August 1995     

Lower Bounds for Fully Dynamic Connectivity Problems in Graphs

We prove lower bounds on the complexity of maintaining fully dynamic k -edge or k -vertex connectivity in plane graphs and in (k-1) -vertex connected graphs. We show an amortized lower bound of (log n / {k (log log n} + log b)) per edge insertion, deletion, or query operation in the cell probe model, where b is the word size of the machine and n is the number of vertices in G . We also show an amortized lower bound of (log n /(log log n + log b)) per operation for fully dynamic planarity testing in embedded graphs. These are the first lower bounds for fully dynamic connectivity problems. Received January 1995; revised February 1997.     

Partition arguments in multiparty communication complexity

Consider the “Number in Hand” multiparty communication complexity model, where k players holding inputs x₁,…,x_k∈{0,1}ⁿ communicate to compute the value f(x₁,…,x_k) of a function f known to all of them. The main lower bound technique for the communication complexity of such problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem.In this paper, we study the power of partition arguments. Our two main results are very different in nature:

(i)

For randomized communication complexity, we show that partition arguments may yield bounds that are exponentially far from the true communication complexity. Specifically, we prove that there exists a 3-argument function f whose communication complexity is Ω(n), while partition arguments can only yield an Ω(logn) lower bound. The same holds for nondeterministiccommunication complexity.

(ii)

For deterministic communication complexity, we prove that finding significant gaps between the true communication complexity and the best lower bound that can be obtained via partition arguments, would imply progress on a generalized version of the “log-rank conjecture” in communication complexity. We also observe that, in the case of computing relations (search problems), very large gaps do exist.

We conclude with two results on the multiparty “fooling set technique”, another method for obtaining communication complexity lower bounds.     

A lower bound on the mod 6 degree of the OR function

We examine the computational power of modular counting, where the modulus m is not a prime power, in the setting of polynomials in Boolean variables over Z _m . In particular, we say that a polynomial P weakly represents a Boolean function f (both have n variables) if for any inputs x and y in {0,1}ⁿ, we have whenever . Barrington et al. (1994) investigated the minimal degree of a polynomial representing the OR function in this way, proving an upper bound of O(n ^{1/ r} ) (where r is the number of distinct primes dividing m) and a lower bound of . Here, we show a lower bound of when m is a product of two primes and in general. While many lower bounds are known for a much stronger form of representation of a function by a polynomial (Barrington et al. 1994, Tsai 1996), very little is known using this liberal (and, we argue, more natural) definition. While the degree is known to be for the generalized inner product because of its high communication complexity (Grolmusz 1995), our bound is the best known for any function of low communication complexity and any modulus not a prime power. received 29 September 1994     

Strong computational lower bounds via parameterized complexity

We develop new techniques for deriving strong computational lower bounds for a class of well-known NP-hard problems. This class includes weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. For example, although a trivial enumeration can easily test in time O(nk) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k)no(k) for any function f, even if we restrict the parameter values to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be of the order Θ(μ(n)) for any reasonable function μ, no algorithm of running time no(k) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds on the computational complexity are also derived for other NP-hard problems in the above class. Our techniques can be further extended to derive computational lower bounds on polynomial time approximation schemes for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1/?)no(1/?) for any function f unless an unlikely collapse occurs in parameterized complexity theory.     

Adaptive versus nonadaptive queries to NP and p-selective sets

We prove that P = NP follows if for some , the class of functions that are computable in polynomial time by nonadaptively accessing an oracle in NP is effectively included in PF^NP[k⌈log n⌉— 1], the class of functions that are computable in polynomial k⌈log n⌉— 1 queries to an oracle in NP.?We draw several observations and relationships between the following two properties of a complexity class : whether there exists a truthtable hard p-selective language for , and whether polynomially-many nonadaptive queries to can be answered by making O(log n)-many adaptive queries to (in symbols, whether ). Among these, we show that if there exists an NP-hard p-selective set under truth-table reductions, then . However, if , then these two properties are equivalent. Received: November 1, 1996.     

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.     

Bounded-Depth Circuits Cannot Sample Good Codes

We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We prove a lower bound of 1 ? 1/n ^??(1) on the statistical distance between (i) the output distribution of any small constant-depth (a.k.a. AC⁰) circuit f : {0, 1}^poly(n) ?? {0, 1} ⁿ , and (ii) the uniform distribution over any code ${\mathcal{C} \subseteq \{0, 1\}^n}$ that is ??good,?? that is, has relative distance and rate both ??(1). This seems to be the first lower bound of this kind. We give two simple applications of this result: (1) any data structure for storing codewords of a good code ${\mathcal{C} \subseteq \{0, 1\}^n}$ requires redundancy ??(log n), if each bit of the codeword can be retrieved by a small AC⁰ circuit; and (2) for some choice of the underlying combinatorial designs, the output distribution of Nisan??s pseudorandom generator against AC⁰ circuits of depth d cannot be sampled by small AC⁰ circuits of depth less than d.     

一类可分离SAT问题的O(1.890n)精确算法

布尔可满足性问题（SAT）是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT）,从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O（（2-2/k）ⁿ）,当k=3时,最好算法时间复杂度为O（1.308ⁿ）.而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题（3-RSSAT）,证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O（1.890ⁿ）判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O（1.890ⁿ）精确算法,该算法与子句长度无关.     

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.     

Monte Carlo circuits for the abelian permutation group intersection problem

Summary We show that the problem of computing a basis for an abelian transitive permutation group is in N C ^k and also we show that the problem of computing a basis for an abelian permutation group and the problem of computing the intersection of two abelian groups acting on n points, can be solved in depth (log n)^k on a Monte Carlo Boolean circuit of polynomial size. Moreover the latter two problems are shown to be in N C ^k in the restricted case of bounded number of generators.