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->{-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.
Abstract We study the approximation of halfspaces h:{0,1}n→{0,1} h : { 0 , 1 } n → { 0 , 1 } in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the “hardest” halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all halfspaces. This completes a lengthy line of work started by Myhill and Kautz (1961). As an application, we construct a communication problem that achieves essentially the largest possible separation, of O(n) versus 2−Ω(n) 2 - Ω ( n ) , between the sign-rank and discrepancy. Equivalently, our problem exhibits a gap of log n versus Ω(n) Ω ( n ) between the communication complexity with unbounded versus weakly unbounded error, improving quadratically on previous constructions and completing a line of work started by Babai, Frankl, and Simon (FOCS 1986). Our results further generalize to the k-party number-on-the-forehead model, where we obtain an explicit separation of log n versus Ω(n/4n) Ω ( n / 4 n ) for communication with unbounded versus weakly unbounded error.
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.
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). In a seminal 1969 monograph, Minsky and Papert constructed a polynomial-size constant-depth {∧, ∨)-circuit in n variables with threshold degree Ω(n1/3). This bound underlies some of today's strongest results on constant-depth circuits. It has been an open problem (O'Donnell and Servedio, STOC 2003) to improve Minsky and Papert's bound to nΩ(1)+1/3.
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
The ε-approximate degree of a Boolean function f:{−1,1}n→{−1,1} is the minimum degree of a real polynomial that approximates f to within ε in the ℓ∞ norm. We prove several lower bounds on this important complexity measure by explicitly constructing solutions to the dual of an appropriate linear program. Our first result resolves the ε-approximate degree of the two-level AND-OR tree for any constant ε>0. We show that this quantity is Θ(n), closing a line of incrementally larger lower bounds. The same lower bound was recently obtained independently by Sherstov using related techniques. Our second result gives an explicit dual polynomial that witnesses a tight lower bound for the approximate degree of any symmetric Boolean function, addressing a question of Špalek. Our final contribution is to reprove several Markov-type inequalities from approximation theory by constructing explicit dual solutions to natural linear programs. These inequalities underly the proofs of many of the best-known approximate degree lower bounds, and have important uses throughout theoretical computer science.
The approximate non-deterministic degree of a Boolean function f, denoted ndegε(f) (written Nε(f) for brevity), is the minimum degree of a real polynomial p such that 0≤∣p(x)∣≤ε whenever f(x)=0, and ∣p(x)∣≥1 whenever f(x)=1. Unlike exact non-deterministic degree, which only requires the polynomial to be nonzero on 1-inputs, this measure enforces a uniform gap: the polynomial must stay close to zero on all 0-inputs and bounded away from zero on all 1-inputs.
The rational degree conjecture, open for over three decades, was recently resolved by Kothari, Kovacs-Deak, Wang, and Yang, who showed that for every total Boolean function f, deg(f)≤O(rdeg(f)3).
In their paper, they explicitly propose a stronger conjecture: that approximate degree is polynomially bounded by Nε(f) and Nε(f) jointly, i.e., for every total Boolean function f and every constant 0<ε<1, deg(f)≤poly(Nε(f),Nε(f)).
This conjecture, if true, would imply a polynomial version of the rational degree result and bring us closer to resolving de Wolf's longstanding non-deterministic degree conjecture.
In this work, we make the first systematic progress on this problem, establishing the conjecture for several broad and natural function classes: monotone and unate functions, functions of bounded alternation number, symmetric functions, k-uniform hypergraph properties, and read-k Disjunctive Normal Form (DNF) formulas.