Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1902.01765 · Computational Complexity

The hardest halfspace

Alexander A. Sherstov

Published Aug 3, 2021• 6 citations
arXivHTMLPDF

Abstract

Abstract We study the approximation of halfspaces $$h:\{0,1\}^n\to\{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^{-\Omega(n)}$$ 2 - Ω ( n ) , between the sign-rank and discrepancy. Equivalently, our problem exhibits a gap of log n versus $$\Omega(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 $$\Omega(n/4^{n})$$ Ω ( n / 4 n ) for communication with unbounded versus weakly unbounded error.

DOI
10.1007/s00037-021-00211-4

Related papers

The Large-Error Approximate Degree of AC^0

Mark Bun, Justin Thaler

We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight Omega~(n^{1/2}) lower bound on the threshold degree of the SURJECTIVITY function on n variables. This matches the best known threshold degree bound for any AC^0 function, previously exhibited by a much more complicated circuit of larger depth (Sherstov, FOCS 2015). Our result also extends to a 2^{Omega~(n^{1/2})} lower bound on the sign-rank of an AC^0 function, improving on the previous best bound of 2^{Omega(n^{2/5})} (Bun and Thaler, ICALP 2016). Second, for any delta>0, we exhibit a function f : {-1,1}^n -> {-1,1} that is computed by a circuit of depth O(1/delta) and is hard to approximate by polynomials in the following sense: f cannot be uniformly approximated to error epsilon=1-2^{-Omega(n^{1-delta})}, even by polynomials of degree n^{1-delta}. Our recent prior work (Bun and Thaler, FOCS 2017) proved a similar lower bound, but which held only for error epsilon=1/3. Our result implies 2^{Omega(n^{1-delta})} lower bounds on the complexity of AC^0 under a variety of basic measures such as discrepancy, margin complexity, and threshold weight. This nearly matches the trivial upper bound of 2^{O(n)} that holds for every function. The previous best lower bound on AC^0 for these measures was 2^{Omega(n^{1/2})} (Sherstov, FOCS 2015). Additional applications in learning theory, communication complexity, and cryptography are described.

Leibniz international proceedings in informatics•Jan 1, 2019•3 citations

Lower bounds in communication complexity and learning theory via analytic methods

Adam R. Klivans, Alexander A. Sherstov

A central goal of theoretical computer science is to characterize the limits of efficient computation in a variety of models. We pursue this research objective in the contexts of communication complexity and computational learning theory. In the former case, one seeks to understand which distributed computations require a significant amount of communication among the parties involved. In the latter case, one aims to rigorously explain why computers cannot master some prediction tasks or learn from past experience. While communication and learning may seem to have little in common, they turn out to be closely related, and much insight into both can be gained by studying them jointly. Such is the approach pursued in this thesis. We answer several fundamental questions in communication complexity and learning theory and in so doing discover new relations between the two topics. A consistent theme in our work is the use of analytic methods to solve the problems at hand, such as approximation theory, Fourier analysis, matrix analysis, and duality. (1) We contribute a novel technique, the pattern matrix method , for proving lower bounds on communication. Using our method, we solve an open problem due to Krause and Pudlak (1997) on the comparative power of two well-studied circuit classes: majority circuits and constant-depth AND/OR/NOT circuits. Next, we prove that the pattern matrix method applies not only to classical communication but also to the more powerful quantum model. In particular, we contribute lower bounds for a new class of quantum communication problems, broadly subsuming the celebrated work by Razborov (2002) who used different techniques. In addition, our method has enabled considerable progress by a number of researchers in the area of multiparty communication. (2) Second, we study unbounded-error communication, a natural model with applications to matrix analysis, circuit complexity, and learning. We obtain essentially optimal lower bounds for all symmetric functions, giving the first strong results for unbounded-error communication in years. Next, we resolve a longstanding open problem due to Babai, Frankl, and Simon (1986) on the comparative power of unbounded-error communication and alternation, showing that Scc2n UPPCC: The latter result also yields an unconditional, exponential lower bound for learning DNF formulas by a large class of algorithms, which explains why this central problem in computational learning theory remains open after more than 20 years of research. (3) We establish the computational intractability of learning intersections of halfspaces, a major unresolved challenge in computational learning theory. Specifically, we obtain the first exponential, near-optimal lower bounds for the learning complexity of this problem in Kearns’ statistical query model, Valiant’s PAC model (under standard cryptographic assumptions), and various analytic models. We also prove that the intersection of even two half-spaces on {0, 1}n cannot be sign-represented by a polynomial of degree less than Qpnp , which is an exponential improvement on previous lower bounds and solves an open problem due to Klivans (2002). (4) We fully determine the relations and gaps among three key complexity measures of a communication problem: product discrepancy, sign-rank, and discrepancy. As an application, we solve an open problem due to Kushilevitz and Nisan (1997) on distributional complexity under product versus nonproduct distributions, as well as separate the communication classes PPCC and UPP CC due to Babai, Frankl, and Simon (1986). We give interpretations of ourresults in purely learning-theoretic terms.

•Jan 1, 2009•3 citations

Dual polynomials and communication complexity of $\textsf{XOR}$ functions

Arkadev Chattopadhyay, Nikhil S. Mande

We show a new duality between the polynomial margin complexity of $f$ and the discrepancy of the function $f \circ \textsf{XOR}$, called an $\textsf{XOR}$ function. Using this duality, we develop polynomial based techniques for understanding the bounded error ($\textsf{BPP}$) and the weakly-unbounded error ($\textsf{PP}$) communication complexities of $\textsf{XOR}$ functions. We show the following. A weak form of an interesting conjecture of Zhang and Shi (Quantum Information and Computation, 2009) (The full conjecture has just been reported to be independently settled by Hatami and Qian (Arxiv, 2017). However, their techniques are quite different and are not known to yield many of the results we obtain here). Zhang and Shi assert that for symmetric functions $f : \{0, 1\}^n \rightarrow \{-1, 1\}$, the weakly unbounded-error complexity of $f \circ \textsf{XOR}$ is essentially characterized by the number of points $i$ in the set $\{0,1, \dots,n-2\}$ for which $D_f(i) \neq D_f(i+2)$, where $D_f$ is the predicate corresponding to $f$. The number of such points is called the odd-even degree of $f$. We show that the $\textsf{PP}$ complexity of $f \circ \textsf{XOR}$ is $Ω(k/ \log(n/k))$. We resolve a conjecture of a different Zhang characterizing the Threshold of Parity circuit size of symmetric functions in terms of their odd-even degree. We obtain a new proof of the exponential separation between $\textsf{PP}^{cc}$ and $\textsf{UPP}^{cc}$ via an $\textsf{XOR}$ function. We provide a characterization of the approximate spectral norm of symmetric functions, affirming a conjecture of Ada et al. (APPROX-RANDOM, 2012) which has several consequences. Additionally, we prove strong $\textsf{UPP}$ lower bounds for $f \circ \textsf{XOR}$, when $f$ is symmetric and periodic with period $O(n^{1/2-ε})$, for any constant $ε> 0$.

arXiv:1704.02537•Apr 8, 2017•2 citations

Communication Lower Bounds Using Dual Polynomials

Alexander A. Sherstov

Representations of Boolean functions by real polynomials play an important role in complexity theory. Typically, one is interested in the least degree of a polynomial p(x_1,...,x_n) that approximates or sign-represents a given Boolean function f(x_1,...,x_n). This article surveys a new and growing body of work in communication complexity that centers around the dual objects, i.e., polynomials that certify the difficulty of approximating or sign-representing a given function. We provide a unified guide to the following results, complete with all the key proofs: (1) Sherstov's Degree/Discrepancy Theorem, which translates lower bounds on the threshold degree of a Boolean function into upper bounds on the discrepancy of a related function; (2) Two different methods for proving lower bounds on bounded-error communication based on the approximate degree: Sherstov's pattern matrix method and Shi and Zhu's block composition method; (3) Extension of the pattern matrix method to the multiparty model, obtained by Lee and Shraibman and by Chattopadhyay and Ada, and the resulting improved lower bounds for DISJOINTNESS; (4) David and Pitassi's separation of NP and BPP in multiparty communication complexity for k=(1-eps)log n players.

arXiv:0805.2135•Electronic colloquium on computational complexity•May 14, 2008•56 citations

Approximation norms and duality for communication complexity lower bounds

Troy Lee, Adi Shraibman

Abstract: We will discuss a general norm based framework for showing lower bounds on communication complexity. An advantage of this approach is that one can use duality theory to obtain a lower bound quantity phrased as a maximization problem, which can be more convenient to work with in showing lower bounds. We discuss two applications of this approach. 1. The approximation rank of a matrix A is the minimum rank of a matrix close to A in ell_infty norm. The logarithm of approximation rank lower bounds quantum communication complexity and is one of the most powerful techniques available, albeit difficult to compute in practice. We show that an approximation norm known as gamma_2 is polynomially related to approximation rank. This results in a polynomial time algorithm to approximate approximation rank, and also shows that the logarithm of approximation rank lower bounds quantum communication complexity even with entanglement which was previously not known. 2. By means of an approximation norm which lower bounds multiparty number-on-the-forehead complexity, we show non-trivial lower bounds on the complexity of the disjointness function for up to c log log n players, c <1.

Dagstuhl Seminar Proceedings•Jan 1, 2008•0 citations

Testing +/- 1-Weight Halfspaces

Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld +1 more

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

•Jan 1, 2009•1 citation
Abstract We study the approximation of halfspaces h:{0,1}n→{0,1}h:\{0,1\}^n\to\{0,1\}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^{-\Omega(n)}2−Ω(n) 2 - Ω ( n ) , between the sign-rank and discrepancy. Equivalently, our problem exhibits a gap of log n versus Ω(n)\Omega(n)Ω(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)\Omega(n/4^{n})Ω(n/4n) Ω ( n / 4 n ) for communication with unbounded versus weakly unbounded error.
We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight Omega~(n^{1/2}) lower bound on the threshold degree of the SURJECTIVITY function on n variables. This matches the best known threshold degree bound for any AC^0 function, previously exhibited by a much more complicated circuit of larger depth (Sherstov, FOCS 2015). Our result also extends to a 2^{Omega~(n^{1/2})} lower bound on the sign-rank of an AC^0 function, improving on the previous best bound of 2^{Omega(n^{2/5})} (Bun and Thaler, ICALP 2016). Second, for any delta>0, we exhibit a function f : {-1,1}^n -> {-1,1} that is computed by a circuit of depth O(1/delta) and is hard to approximate by polynomials in the following sense: f cannot be uniformly approximated to error epsilon=1-2^{-Omega(n^{1-delta})}, even by polynomials of degree n^{1-delta}. Our recent prior work (Bun and Thaler, FOCS 2017) proved a similar lower bound, but which held only for error epsilon=1/3. Our result implies 2^{Omega(n^{1-delta})} lower bounds on the complexity of AC^0 under a variety of basic measures such as discrepancy, margin complexity, and threshold weight. This nearly matches the trivial upper bound of 2^{O(n)} that holds for every function. The previous best lower bound on AC^0 for these measures was 2^{Omega(n^{1/2})} (Sherstov, FOCS 2015). Additional applications in learning theory, communication complexity, and cryptography are described.
A central goal of theoretical computer science is to characterize the limits of efficient computation in a variety of models. We pursue this research objective in the contexts of communication complexity and computational learning theory. In the former case, one seeks to understand which distributed computations require a significant amount of communication among the parties involved. In the latter case, one aims to rigorously explain why computers cannot master some prediction tasks or learn from past experience. While communication and learning may seem to have little in common, they turn out to be closely related, and much insight into both can be gained by studying them jointly. Such is the approach pursued in this thesis. We answer several fundamental questions in communication complexity and learning theory and in so doing discover new relations between the two topics. A consistent theme in our work is the use of analytic methods to solve the problems at hand, such as approximation theory, Fourier analysis, matrix analysis, and duality. (1) We contribute a novel technique, the pattern matrix method , for proving lower bounds on communication. Using our method, we solve an open problem due to Krause and Pudlak (1997) on the comparative power of two well-studied circuit classes: majority circuits and constant-depth AND/OR/NOT circuits. Next, we prove that the pattern matrix method applies not only to classical communication but also to the more powerful quantum model. In particular, we contribute lower bounds for a new class of quantum communication problems, broadly subsuming the celebrated work by Razborov (2002) who used different techniques. In addition, our method has enabled considerable progress by a number of researchers in the area of multiparty communication. (2) Second, we study unbounded-error communication, a natural model with applications to matrix analysis, circuit complexity, and learning. We obtain essentially optimal lower bounds for all symmetric functions, giving the first strong results for unbounded-error communication in years. Next, we resolve a longstanding open problem due to Babai, Frankl, and Simon (1986) on the comparative power of unbounded-error communication and alternation, showing that Scc2n UPPCC: The latter result also yields an unconditional, exponential lower bound for learning DNF formulas by a large class of algorithms, which explains why this central problem in computational learning theory remains open after more than 20 years of research. (3) We establish the computational intractability of learning intersections of halfspaces, a major unresolved challenge in computational learning theory. Specifically, we obtain the first exponential, near-optimal lower bounds for the learning complexity of this problem in Kearns’ statistical query model, Valiant’s PAC model (under standard cryptographic assumptions), and various analytic models. We also prove that the intersection of even two half-spaces on {0, 1}n cannot be sign-represented by a polynomial of degree less than Qpnp , which is an exponential improvement on previous lower bounds and solves an open problem due to Klivans (2002). (4) We fully determine the relations and gaps among three key complexity measures of a communication problem: product discrepancy, sign-rank, and discrepancy. As an application, we solve an open problem due to Kushilevitz and Nisan (1997) on distributional complexity under product versus nonproduct distributions, as well as separate the communication classes PPCC and UPP CC due to Babai, Frankl, and Simon (1986). We give interpretations of ourresults in purely learning-theoretic terms.
Dual polynomials and communication complexity of XOR\textsf{XOR}XOR functions
We show a new duality between the polynomial margin complexity of fff and the discrepancy of the function f∘XORf \circ \textsf{XOR}f∘XOR, called an XOR\textsf{XOR}XOR function. Using this duality, we develop polynomial based techniques for understanding the bounded error (BPP\textsf{BPP}BPP) and the weakly-unbounded error (PP\textsf{PP}PP) communication complexities of XOR\textsf{XOR}XOR functions. We show the following. A weak form of an interesting conjecture of Zhang and Shi (Quantum Information and Computation, 2009) (The full conjecture has just been reported to be independently settled by Hatami and Qian (Arxiv, 2017). However, their techniques are quite different and are not known to yield many of the results we obtain here). Zhang and Shi assert that for symmetric functions f:{0,1}n→{−1,1}f : \{0, 1\}^n \rightarrow \{-1, 1\}f:{0,1}n→{−1,1}, the weakly unbounded-error complexity of f∘XORf \circ \textsf{XOR}f∘XOR is essentially characterized by the number of points iii in the set {0,1,…,n−2}\{0,1, \dots,n-2\}{0,1,…,n−2} for which Df(i)≠Df(i+2)D_f(i) \neq D_f(i+2)Df​(i)=Df​(i+2), where DfD_fDf​ is the predicate corresponding to fff. The number of such points is called the odd-even degree of fff. We show that the PP\textsf{PP}PP complexity of f∘XORf \circ \textsf{XOR}f∘XOR is Ω(k/log⁡(n/k))Ω(k/ \log(n/k))Ω(k/log(n/k)). We resolve a conjecture of a different Zhang characterizing the Threshold of Parity circuit size of symmetric functions in terms of their odd-even degree. We obtain a new proof of the exponential separation between PPcc\textsf{PP}^{cc}PPcc and UPPcc\textsf{UPP}^{cc}UPPcc via an XOR\textsf{XOR}XOR function. We provide a characterization of the approximate spectral norm of symmetric functions, affirming a conjecture of Ada et al. (APPROX-RANDOM, 2012) which has several consequences. Additionally, we prove strong UPP\textsf{UPP}UPP lower bounds for f∘XORf \circ \textsf{XOR}f∘XOR, when fff is symmetric and periodic with period O(n1/2−ε)O(n^{1/2-ε})O(n1/2−ε), for any constant ε>0ε> 0ε>0.
Representations of Boolean functions by real polynomials play an important role in complexity theory. Typically, one is interested in the least degree of a polynomial p(x_1,...,x_n) that approximates or sign-represents a given Boolean function f(x_1,...,x_n). This article surveys a new and growing body of work in communication complexity that centers around the dual objects, i.e., polynomials that certify the difficulty of approximating or sign-representing a given function. We provide a unified guide to the following results, complete with all the key proofs: (1) Sherstov's Degree/Discrepancy Theorem, which translates lower bounds on the threshold degree of a Boolean function into upper bounds on the discrepancy of a related function; (2) Two different methods for proving lower bounds on bounded-error communication based on the approximate degree: Sherstov's pattern matrix method and Shi and Zhu's block composition method; (3) Extension of the pattern matrix method to the multiparty model, obtained by Lee and Shraibman and by Chattopadhyay and Ada, and the resulting improved lower bounds for DISJOINTNESS; (4) David and Pitassi's separation of NP and BPP in multiparty communication complexity for k=(1-eps)log n players.
Abstract: We will discuss a general norm based framework for showing lower bounds on communication complexity. An advantage of this approach is that one can use duality theory to obtain a lower bound quantity phrased as a maximization problem, which can be more convenient to work with in showing lower bounds. We discuss two applications of this approach. 1. The approximation rank of a matrix A is the minimum rank of a matrix close to A in ell_infty norm. The logarithm of approximation rank lower bounds quantum communication complexity and is one of the most powerful techniques available, albeit difficult to compute in practice. We show that an approximation norm known as gamma_2 is polynomially related to approximation rank. This results in a polynomial time algorithm to approximate approximation rank, and also shows that the logarithm of approximation rank lower bounds quantum communication complexity even with entanglement which was previously not known. 2. By means of an approximation norm which lower bounds multiparty number-on-the-forehead complexity, we show non-trivial lower bounds on the complexity of the disjointness function for up to c log log n players, c <1.
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