ACM Symposium on Theory of Computing (STOC)

The expressive power of voting polynomials

James Aspnes, Richard Beigel, Merrick Furst, Steven Rudich

Published Jan 1, 1991• 60 citations

Abstract

We consider the problem of approximating a Boolean function f : f0; 1g n ! f0; 1g by the sign of an integer polynomial p of degree k. For us, a polynomial p(x) predicts the value of f(x) if, whenever p(x) 0, f(x) = 1, and whenever p(x) ! 0, f(x) = 0. A low-degree polynomial p is a good approximator for f if it predicts f at almost all points. Given a positive integer k, and a Boolean function f , we ask, "how good is the best degree k approximation to f?" We introduce a new lower bound technique which applies to any Boolean function. We show that the lower bound technique yields tight bounds in the case f is parity. Minsky and Papert [10] proved that a perceptron can not compute parity; our bounds indicate exactly how well Yale University, Dept. of Computer Science, P.O. Box 208285, New Haven CT 06520-8285. y Email: aspnes-james@cs.yale.edu. z Email: beigel-richard@cs.yale.edu. Supported in part by NSF grants CCR-8808949 and CCR-8958528. x Carnegie-Mellon University, Schoo...

DOI: 10.1145/103418.103461

Related papers

Lower Bounds for the Approximate Degree of Block-Composed Functions

Justin Thaler

We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function f on N bits, define F(x_1,...,x_M) = OMB(f(x_1),...,f(x_M)) to be the function on M*N bits obtained by block-composing f with a function known as ODD-MAX-BIT. We show that, if f requires large degree to approximate to error 2/3 in a certain one-sided sense (captured by a complexity measure known as positive one-sided approximate degree), then F requires large degree to approximate even to error 1-2^{-M}. This generalizes a result of Beigel (Computational Complexity, 1994), who proved an identical result for the special case f=OR. Unlike related prior work, our result implies strong approximate degree lower bounds even for many functions F that have low threshold degree. Our proof is constructive: we exhibit a solution to the dual of an appropriate linear program capturing the approximate degree of any function. We describe several applications, including improved separations between the complexity classes P^{NP} and PP in both the query and communication complexity settings. Our separations improve on work of Beigel (1994) and Buhrman, Vereshchagin, and de Wolf (CCC, 2007).

Leibniz international proceedings in informaticsJan 1, 201615 citations

On the degree of polynomials that approximate symmetric Boolean functions (preliminary version)

Ramamohan Paturi

In this paper, we provide matching (up to a constant factor) upper and lower bounds on the degree of polynomials that represent symmetric boolean functions with an error 1/3. Let Γ(f)=min{|2k–n+1|:fk ≠ fk+ 1 and 0 ≤ k ≤ n – 1} where fi is the value of f on inputs with exactly i 1's. We prove that the minimum degree over all the approximating polynomials of f is Θ((n(n-Γ(f))).5). We apply the techniques and tools from approximation theory to derive this result.

ACM Symposium on Theory of Computing (STOC)Jan 1, 1992152 citations

Approximating the AND-OR Tree.

Alexander A. Sherstov

ABSTRACT. The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f within 1=3 at every point. We prove that the functionVn iD1 Wn jD1 xij, known as the AND-OR tree, has approximate degree˝.n/: This lower bound is tight and closes a line of research on the problem, the best previous bound being ˝.n0:75/. More generally, we prove that the function

Electronic colloquium on computational complexityJan 1, 20133 citations

The Power of Asymmetry in Constant-Depth Circuits

Alexander A. Sherstov

The threshold degree of a Boolean function f is the minimum degree of a real polynomial p that represents f in sign: f(x) = sgn p(x). Introduced in the seminal work of Minsky and Papert (1969), this notion is central to some of the strongest algorithmic and complexity-theoretic results for constant-depth circuits. One problem that has remained open for several decades, with applications to computational learning and communication complexity, is to determine the maximum threshold degree of a polynomial-size constant-depth circuit in n variables. The best lower bound prior to our work was Ω(n(d-1)/(2d-1)) for circuits of depth d. We obtain a polynomial improvement for every depth d, with a lower bound of Ω(n3/7) for depth 3 and Ω(√n) for depth d ≥4. The proof contributes a novel approximation-theoretic technique of independent interest, which exploits asymmetry in circuits to prove their hardness for polynomials.

Annual Symposium on Foundations of Computer ScienceOct 1, 201514 citations

Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions

Servedio, Rocco

We give a deterministic algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-2 polynomial threshold function. Given a degree-2 input polynomial p(x1, . . . , xn) and a parameter > 0, the algorithm approximates Prx∼{−1,1}n [p(x) ≥ 0] to within an additive ± in time poly(n, 2 ). Note that it is NP-hard to determine whether the above probability is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. This is the first deterministic algorithm for this counting problem in which the running time is polynomial in n for = o(1). For “regular” polynomials p (those in which no individual variable’s influence is large compared to the sum of all n variable influences) our algorithm runs in poly(n, 1/ ) time. The algorithm also runs in poly(n, 1/ ) time to approximate Prx∼N(0,1)n [p(x) ≥ 0] to within an additive ± , for any degree-2 polynomial p. As an application of our counting result, we give a deterministic FPT multiplicative (1± )-approximation algorithm to approximate the k-th absolute moment Ex∼{−1,1}n [|p(x)|] of a degree-2 polynomial. The algorithm’s running time is of the form poly(n) · f(k, 1/ ). ∗anindya@math.ias.edu. Research supported by Templeton Foundation Grant 21674 and NSF CCF-1149843. †ilias.d@ed.ac.uk. Some of this work was done while the author was at UC Berkeley supported by a Simons Fellowship. ‡rocco@cs.columbia.edu. Supported by NSF grants CNS-0716245, CCF-0915929, and CCF-1115703. ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Report No. 172 (2013)

Jan 1, 20141 citation

Boolean Functions of Low Polynomial Degree for Quantum Query Complexity Theory

Rūsiņš Freivalds, Liva Garkaje

The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. This is why Boolean functions are needed with a high number of essential variables and a low polynomial degree. Unfortunately, it is a well-known problem to construct such functions. The best separation between these two complexity measures of a Boolean function was exhibited by Ambai- nis [5]. He constructed functions with polynomial degree M and number of variables Omega(M2). We improve such a separation to become exponential. On the other hand, we use a computerized exhaustive search to prove tightness of this bound.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)May 1, 20070 citations