The Chow parameters of a Boolean function f: {-1,1}n -> {-1,1} are its n+1 degree-0 and degree-1 Fourier coefficients. It has been known since 1961 [Cho61, Tan61] that the (exact values of the) Chow parameters of any linear threshold function f uniquely specify f within the space of all Boolean functions, but until recently [OS11] nothing was known about efficient algorithms for reconstructing f (exactly or approximately) from exact or approximate values of its Chow parameters. We refer to this reconstruction problem as the Chow Parameters Problem. Our main result is a new algorithm for the Chow Parameters Problem which, given (sufficiently accurate approximations to) the Chow parameters of any linear threshold function f, runs in time ~O(n2)• (1/ε)O(log2(1/ε)) and with high probability outputs a representation of an LTF f' that is ε-close to f. The only previous algorithm [OS11] had running time poly(n) • 22~O(1/ε2).
The Chow parameters of a Boolean function f: {-1,1}n -> {-1,1} are its n+1 degree-0 and degree-1 Fourier coefficients. It has been known since 1961 [Cho61, Tan61] that the (exact values of the) Chow parameters of any linear threshold function f uniquely specify f within the space of all Boolean functions, but until recently [OS11] nothing was known about efficient algorithms for reconstructing f (exactly or approximately) from exact or approximate values of its Chow parameters. We refer to this reconstruction problem as the Chow Parameters Problem. Our main result is a new algorithm for the Chow Parameters Problem which, given (sufficiently accurate approximations to) the Chow parameters of any linear threshold function f, runs in time O(n2)• (1/ε)O(log2(1/ε)) and with high probability outputs a representation of an LTF f' that is ε-close to f. The only previous algorithm [OS11] had running time poly(n) • 22O(1/ε2).
The degree-d Chow parameters of a Boolean function are its degree at most d Fourier coefficients. It is well-known that degree-d Chow parameters uniquely characterize degree-d polynomial threshold functions (PTFs) within the space of all bounded functions. In this paper, we prove a robust version of this theorem: For f any Boolean degree-d PTF and g any bounded function, if the degree-d Chow parameters of f are close to the degree-d Chow parameters of g in ℓ2-norm, then f is close to g in ℓ1-distance. Notably, our bound relating the two distances is independent of the dimension. That is, we show that Boolean degree-d PTFs are robustly identifiable from their degree-d Chow parameters. No non-trivial bound was previously known for d >1.
The threshold degree of a Boolean function f:{0,1}^n->{-1,+1} is the least degree of a real polynomial p such that f(x)=sgn p(x). We construct two halfspaces on {0,1}^n whose intersection has threshold degree Theta(sqrt n), an exponential improvement on previous lower bounds. This solves an open problem due to Klivans (2002) and rules out the use of perceptron-based techniques for PAC learning the intersection of two halfspaces, a central unresolved challenge in computational learning. We also prove that the intersection of two majority functions has threshold degree Omega(log n), which is tight and settles a conjecture of O'Donnell and Servedio (2003). Our proof consists of two parts. First, we show that for any nonconstant Boolean functions f and g, the intersection f(x)^g(y) has threshold degree O(d) if and only if ||f-F||_infty + ||g-G||_infty < 1 for some rational functions F, G of degree O(d). Second, we settle the least degree required for approximating a halfspace and a majority function to any given accuracy by rational functions. Our technique further allows us to make progress on Aaronson's challenge (2008) and contribute strong direct product theorems for polynomial representations of composed Boolean functions of the form F(f_1,...,f_n). In particular, we give an improved lower bound on the approximate degree of the AND-OR tree.
The threshold degree of a Boolean function f:{0,1}n→{0,1} is the minimum degree of a real polynomial p that represents f in sign: sgnp(x)=(−1)f(x). A related notion is sign-rank, defined for a Boolean matrix F=[Fij] as the minimum rank of a real matrix M with sgnMij=(−1)Fij. Determining the maximum threshold degree and sign-rank achievable by constant-depth circuits (AC0) is a well-known and extensively studied open problem, with complexity-theoretic and algorithmic applications. We give an essentially optimal solution to this problem. For any ε>0, we construct an AC0 circuit in n variables that has threshold degree Ω(n1−ε) and sign-rank exp(Ω(n1−ε)), improving on the previous best lower bounds of Ω(n) and exp(Ω~(n)), respectively. Our results subsume all previous lower bounds on the threshold degree and sign-rank of AC0 circuits of any given depth, with a strict improvement starting at depth 4. As a corollary, we also obtain near-optimal bounds on the discrepancy, threshold weight, and threshold density of AC0, strictly subsuming previous work on these quantities. Our work gives some of the strongest lower bounds to date on the communication complexity of AC0.
Abstract. We consider the problem of testing whether a Boolean function f: {−1, 1} n → {−1, 1} is a ±1-weight halfspace, i.e. a function of the form f(x) = sgn(w1x1+w2x2+ · · ·+wnxn) where the weights wi take values in {−1, 1}. We show that the complexity of this problem is markedly different from the problem of testing whether f is a general halfspace with arbitrary weights. While the latter can be done with a number of queries that is independent of n [7], to distinguish whether f is a ±1-weight halfspace versus ɛ-far from all such halfspaces we prove that nonadaptive algorithms must make Ω(log n) queries. We complement this lower bound with a sublinear upper bound showing that O ( √ n·poly ( 1 ɛ)) queries suffice. 1
Let g : {-1, 1}k→ {-1, 1} be any Boolean function and q1, . . . , qkbe any degree-2 polynomials over {-1, 1}n. We give a deterministic algorithm which, given as input explicit descriptions of g, q1, . . ., qkand an accuracy parameter ϵ > 0, approximates Prx~{-1, 1}n[g(sign(q1(x)), . . . , sign(qk(x))) = 1] to within an additive ±ϵ. For any constant ϵ > 0 and k ≥ 1 the running time of our algorithm is a fixed polynomial in n (in fact this is true even for some not-too-small ϵ = 0n(1) and not-too-large k = ωn(1)). This is the first fixed polynomial-time algorithm that can deterministically approximately count satisfying assignments of a natural class of depth-3 Boolean circuits. Our algorithm extends a recent result [1] which gave a deterministic approximate counting algorithm for a single degree-2 polynomial threshold function sign(q(x)), corresponding to the k = 1 case of our result. Note that even in the k = 1 case it is NP-hard to determine whether Prx~{-1, 1}n[sign(q(x)) = 1] is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. Our algorithm and analysis requires several novel technical ingredients that go significantly beyond the tools required to handle the k = 1 case in [1]. One of these is a new multidimensional central limit theorem for degree-2 polynomials in Gaussian random variables which builds on recent Malliavin-calculus-based results from probability theory. We use this CLT as the basis of a new decomposition technique for k-tuples of degree-2 Gaussian polynomials and thus obtain an efficient deterministic approximate counting algorithm for the Gaussian distribution, i.e., an algorithm for estimating Prx~N(0, 1)n[g(sign(q1(x)), . . . , sign(qk(x))) = 1]. Finally, a third new ingredient is a “regularity lemma” for k-tuples of degree-d polynomial threshold functions. This generalizes both the regularity lemmas of [2], [3] (which apply to a single degree-d polynomial threshold function) and the regularity lemma of Gopalan et al [4] (which applies to a k-tuples of linear threshold functions, i.e., the case d = 1). Our new regularity lemma lets us extend our deterministic approximate counting results from the Gaussian to the Boolean domain.
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)