Abstract. The approximate degree of a Boolean function [Formula: see text] is the minimum degree of a real polynomial [Formula: see text] that approximates [Formula: see text] pointwise: [Formula: see text] for all [Formula: see text]. For every [Formula: see text] we construct conjunctive normal form (CNF) and disjunctive normal form (DNF) formulas of polynomial size with approximate degree [Formula: see text] essentially matching the trivial upper bound of [Formula: see text]. This improves polynomially on previous lower bounds and fully resolves the approximate degree of constant-depth circuits [Formula: see text] a question that has seen extensive research over the past 10 years. Prior to our work, an [Formula: see text] lower bound was known only for [Formula: see text] circuits of depth that grows with [Formula: see text] (M. Bun and J. Thaler, SIAM J. Comput., 49 (2020), pp. FOCS17-59–FOCS17-96). Furthermore, the CNF and DNF formulas that we construct are the simplest possible in that they have constant width. Our proof departs significantly from previous approaches and contributes a novel, number-theoretic method for amplifying approximate degree. Our main result remains valid even for one-sided approximation: for any [Formula: see text], we construct a polynomial-size constant-width CNF formula with one-sided approximate degree [Formula: see text]. We thus obtain the following nearly tight separations: [Formula: see text] versus [Formula: see text] for the one-sided versus two-sided approximate degree of a function and [Formula: see text] versus [Formula: see text] for the one-sided approximate degree of a function [Formula: see text] versus its negation [Formula: see text]. As an application, we essentially settle the communication complexity of [Formula: see text] circuits in the bounded-error quantum model, [Formula: see text]-party number-on-the-forehead randomized model, and [Formula: see text]-party number-on-the-forehead nondeterministic model: we prove that for every [Formula: see text], these models require [Formula: see text], [Formula: see text], and [Formula: see text], respectively, bits of communication even for polynomial-size constant-width CNF formulas. In particular, we show that the multiparty communication class [Formula: see text] can be separated near-optimally from [Formula: see text] and [Formula: see text] by a particularly simple function, a polynomial-size constant-width CNF formula.

We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where$0\leqslant r < R\leqslant n$are given integers and Alice and Bob need to determine whether their respective matrices$A, B\in \mathbb{F}^{n\times n}$satisfy rk$(A+B)=r$versus rk$(A+B)=R$. We show that this problem has commu-nication cost$\Omega(r^{2}\log\vert \mathbb{F}\vert)$, which is optimal. Our lower bound holds even for quantum protocols and even for error probability$\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-r/3})$, which too is optimal because this problem has a two-bit classical protocol with error$\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-\Theta(r)})$. Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integers$r$and$R$, with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspace$S$, Bob has a subspace$T$) and they need to approximate the dimension of the subspace$S+T$generated by$S$and$T$(equivalently, approximate the dimension of$S\cap T$). As an application, we obtain an$\Omega(n^{2}\log\vert \mathbb{F}\vert)/k$memory lower bound for any streaming algorithm with$k$passes that approximates the rank of an input matrix$M\in \mathbb{F}^{n\times n}$within a factor of$\sqrt{2}-\delta$, for any$\delta > 0$. Our result is an exponential improvement in$k$over previous work.

Abstract. We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order [Formula: see text] sum to at most [Formula: see text], where [Formula: see text] is the number of variables, [Formula: see text] is the tree depth, and [Formula: see text] is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal [ Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]. The bounds prior to our work degraded rapidly with [Formula: see text], becoming trivial already at [Formula: see text]. As an application, we obtain, for every integer [Formula: see text], a partial Boolean function on [Formula: see text] bits that has bounded-error quantum query complexity at most [Formula: see text] and randomized query complexity [Formula: see text]. This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis [ SIAM J. Comput., 47 (2018), pp. 982–1038] and Bravyi et al. [ Classical Algorithms for Forrelation, arXiv preprint, 2021]. Prior to our work, the best known separation was polynomially weaker: [Formula: see text] versus [Formula: see text] for any [Formula: see text] [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]. As another application, we obtain an essentially optimal separation of [Formula: see text] versus [Formula: see text] for bounded-error quantum versus randomized communication complexity for any [Formula: see text]. The best previous separation was polynomially weaker: [Formula: see text] versus [Formula: see text] (this is implicit in [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]).

The approximate degree of a Boolean function f∶{0,1}n→{0,1} is the minimum degree of a real polynomial p that approximates f pointwise: |f(x)−p(x)|≤1/3 for all x∈{0,1}n. For any δ>0, we construct DNF and CNF formulas of polynomial size with approximate degree Ω(n1−δ), essentially matching the trivial upper bound of n. This fully resolves the approximate degree of constant-depth circuits (AC0), a question that has seen extensive research over the past 10 years. Prior to our work, an Ω(n1−δ) lower bound was known only for AC0 circuits of depth that grows with 1/δ (Bun and Thaler, FOCS 2017). Furthermore, the DNF and CNF formulas that we construct are the simplest possible in that they have constant width.

We prove that for every decision tree, the absolute values of the Fourier coefficients of given order t≥1 sum to at most (cd/t)t/2(1+logn)(t−1)/2, where n is the number of variables, d is the tree depth, and c>0 is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal (arxiv 2019; FOCS 2020). The bounds prior to our work degraded rapidly with t, becoming trivial already at t=√d.

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.

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a novel, first-principles approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: $O(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}})$ for the $k$-element distinctness problem; $O(n^{1-\frac{1}{k+1}})$ for the $k$-subset sum problem; $O(n^{1-\frac{1}{k+1}})$ for any $k$-DNF or $k$-CNF formula; and $O(n^{3/4})$ for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the $\Theta(n)$ quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree $\Omega(n)$. In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.

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: sgn p(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 sgn Mij=(−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.

The threshold degree of a Boolean function $f\colon{{\{0,1\}}^n}\to{\{0,1\}}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: ${sgn}\,p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with ${sgn}\,M_{ij}=(-1)^{F_{ij}}$. Determining the maximum threshold degree and sign-rank achievable by constant-depth circuits (${AC}^{0}$) 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 $\epsilon>0,$ we construct an ${AC}^{0}$ circuit in $n$ variables that has threshold degree $\Omega(n^{1-\epsilon})$ and sign-rank $\exp(\Omega(n^{1-\epsilon})),$ improving on the previous best lower bounds of $\Omega(\sqrt{n})$ and $\exp(\tilde{\Omega}(\sqrt{n}))$, respectively. Our results subsume all previous lower bounds on the threshold degree and sign-rank of ${AC}^{0}$ 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 ${AC}^{0}$, strictly subsuming previous work on these quantities. Our work gives some of the strongest lower bounds to date on the communication complexity of ${AC}^{0}$.

Interactive coding, pioneered by Schulman (FOCS '92, STOC '93), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman et al. proposed a far-reaching generalization of this model, whereby the adversary can additionally manipulate the channel by removing and inserting symbols. For any ϵ > 0, they showed how to faithfully simulate any protocol in this model with corruption rate up to 1/18 - ϵ, using a constant-size alphabet and a constant-factor overhead in communication. We give an optimal simulation of any protocol in this generalized model of substitutions, insertions, and deletions, tolerating a corruption rate up to 1/4 - ϵ, while keeping the alphabet to a constant size and the communication overhead to a constant factor. This resolves a question due to Gelles (2015). Our corruption tolerance matches an impossibility result for corruption rate 1/4 which holds even for substitutions alone (Braverman and Rao, STOC '11).

The approximate degree of a Boolean function f(x1,x2,…,xn) is the minimum degree of a real polynomial that approximates f pointwise within 1/3. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity.

We study the problem of compressing interactive communication to its information content $I$, defined as the amount of information that the participants learn about each other's inputs. We focus on the canonical setting where the participants' inputs are distributed independently and show how to compress the communication to $O(I\log^{2}I)$ bits, with no dependence on the original communication cost. This result essentially matches the well-known lower bound of $\Omega(I)$ and improves quadratically on previous work [B. Barak, M. Braverman, X. Chen, and A. Rao, SIAM J. Comput., 42 (2013), pp. 1327--1363; M. Braverman, SIAM J. Comput., 44 (2015), pp. 1698--1739; G. Kol, Proceedings of the $48$th Annual ACM Symposium on Theory of Computing, 2016, pp. 987--998]. Our result complements the recent breakthrough of Ganor, Kol, and Raz [ J. ACM, 63 (2016), 46] who show that one cannot achieve compression better than $2^{O(I)}$ in the general case when the participants' inputs are dependent random variables.

The threshold degree of a Boolean function $f$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv {sgn}\ p(x)$. In a seminal 1969 monograph, Minsky and Papert constructed a polynomial-size constant-depth $\{\wedge,\vee\}$-circuit in $n$ variables with threshold degree $\Omega(n^{1/3}).$ This lower bound underlies some of today's strongest results on constant-depth circuits. It has since been an open problem [R. O'Donnell and R. A. Servedio: Proceedings of the 35 th Annual ACM Symposium on Theory of Computing, 2003, pp. 325--334] to improve Minsky and Papert's bound to $n^{\Omega(1)+1/3}.$ We give a detailed solution to this problem. For any fixed $k\geq 1,$ we construct an $\{\wedge,\vee\}$-formula of size $n$ and depth $k$ with threshold degree $\Omega(n^{(k-1)/(2k-1)})$. This lower bound nearly matches a known $O(\sqrt{n})$ upper bound for arbitrary formulas and is exactly tight for “regular” formulas. Our result proves a conjecture due to O'Donnell and Servedio and a different conjecture due to [M. Bun and J. Thaler: Electronic Colloquium on Computational Complexity, Report TR13-151, 2013]. Applications to communication complexity and computational learning are given.

The threshold degree of a Boolean function $f$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv {sgn}~ p(x)$. Introduced in the seminal work of Minsky and Papert [ Perceptrons: An Introduction to Computational Geometry, MIT Press, 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 $\Omega(n^{(d-1)/(2d-1)})$ for circuits of depth $d$. We obtain a polynomial improvement for every depth $d,$ with a lower bound of $\Omega(n^{3/7})$ for depth 3 and $\Omega(\sqrt{n})$ for depth $d\geq4.$ The proof contributes an approximation-theoretic technique of independent interest, which exploits asymmetry in circuits to prove their hardness for polynomials.

Interactive coding, pioneered by Schulman (FOCS 92, STOC 93), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversarys discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky (2015) proposed a far-reaching generalization of this model, whereby the adversary can additionally manipulate the channel by removing and inserting symbols. They showed how to faithfully simulate any protocol in this model with corruption rate up to 1/18, using a constant-size alphabet and a constant-factor overhead in communication. We give an optimal simulation of any protocol in this generalized model of substitutions, insertions, and deletions, tolerating a corruption rate up to 1/4 while keeping the alphabet to a constant size and the communication overhead to a constant factor. Our corruption tolerance matches an impossibility result for corruption rate 1/4 which holds even for substitutions alone (Braverman and Rao, STOC 11).

We consider the problem of distributing a computation between two parties, such that any bounded-communication leakage function applied to the local views of the two parties reveals essentially nothing about the input. This problem can be motivated by the goal of outsourcing computations on sensitive data to two servers in the cloud, where both servers can be simultaneously corrupted by viruses that have a limited communication bandwidth. We present a simple and efficient reduction of the above problem to that of constructing parity-resilient circuits, namely circuits that map an encoded input to an encoded output so that the parity of any subset of the wires is essentially independent of the input. We then construct parity-resilient circuits from circuits that are resilient to local leakage, which can in turn be obtained from protocols for secure multiparty computation. Our main reduction builds on a novel generalization of the ε-biased masking lemma that applies to interactive protocols. Applying the above, we obtain two-party protocols with resilience to bounded-communication leakage either in the information-theoretic setting, relying on random oblivious transfer correlations, or in the computational setting, relying on non-committing encryption which can be based on a variety of standard cryptographic assumptions.

We study the problem of compressing interactive communication to its information content I, defined as the amount of information that the participants learn about each other's inputs. We focus on the case when the participants' inputs are distributed independently and show how to compress the communication to O(I log2I) bits, with no dependence on the original communication cost. This result improves quadratically on previous work by Kol (STOC 2016) and essentially matches the well-known lower bound Ω(I).

In the $k$-party set disjointness problem, the goal is to determine whether given subsets $S_1,S_2,\dots,S_k\subseteq\{1,2,\dots,n\}$ have empty intersection. We study this problem in the number-on-the-forehead model of communication, where the $i$th party knows all the sets except for $S_i,$ and prove a lower bound of $\Omega(n/4^k)^{1/4}$ on the randomized and nondeterministic communication complexity. This lower bound is close to tight. Previous lower bounds for set disjointness with $k\geq3$ parties were weaker than $\Omega(n/2^{k^3})^{1/(k+1)}.$ We also prove that solving $\ell$ instances of set disjointness requires $\ell\cdot\Omega(n/4^k)^{1/4}$ bits of communication, even to achieve correctness probability exponentially close to $1/2.$ This gives the first direct product result for multiparty set disjointness, solving an open problem due to Beame et al. (2005). Finally, we construct a read-once $\{\wedge,\vee\}$-circuit of depth $3$ with exponentially small discrepancy for up to $k\approx\frac12\log n$ parties. This result is optimal with respect to depth and solves an open problem due to Beame and Huynh-Ngoc (FOCS '09), who gave a depth-$6$ construction.

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.

We study the set disjointness problem in the most powerful model of bounded-error communication, the k -party randomized number-on-the-forehead model. We show that set disjointness requires Ω(√n/2 k k ) bits of communication, where n is the size of the universe. Our lower bound generalizes to quantum communication, where it is essentially optimal. Proving this bound was a longstanding open problem even in restricted settings, such as one-way classical protocols with k =4 parties [Wigderson 1997]. The proof contributes a novel technique for lower bounds on multiparty communication, based on directional derivatives of protocols over the reals.

We study the set disjointness problem in the most powerful bounded-error model: the number-on-the-forehead model with k parties and arbitrary classical or quantum communication. We obtain a communication lower bound of Omega(√(n)/2k*k) bits, which is essentially optimal. Proving it was a longstanding open problem even in restricted settings, such as one-way classical protocols with k=4 parties (Wigderson 1997). The proof contributes a novel technique for lower bounds on multiparty communication, based on directional derivatives of communication protocols over the reals.

The threshold degree of a Boolean function $f\!\!\,: \{0,1\}^n \rightarrow \{-1, +1\}$ is the least degree of a real polynomial $p$ such that $f(x)\equiv{{\rm 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 [A Complexity-Theoretic Approach to Learning, Ph.D. thesis, MIT, Cambridge, MA, 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({\rm log}\,n),$ which is tight and settles a conjecture of O'Donnell and Servedio [Proceedings of the $35$th Annual ACM Symposium on Theory of Computing (STOC), 2003, pp. 325--334]. Our proof consists of two parts. First, we show that for any nonconstant Boolean functions $f$ and $g,$ the intersection $f(x)\wedge 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 determine 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 obtain direct sum theorems for polynomial representations of composed Boolean functions. In particular, we give an improved lower bound on the approximate degree of the AND-OR tree.

We study the set disjointness problem in the number-on-the-forehead model of multiparty communication.

A basic question in any computational model is how to reliably compute a given function when the inputs or intermediate computations are subject to noise at a constant rate. Ideally, one would like to use at most a constant factor more resources compared to the noise-free case. This question has been studied for decision trees, circuits, automata, data structures, broadcast networks, communication protocols, and other models.

A strong direct product theorem (SDPT) states that solving n instances of a problem requires Omega(n) times the resources for a single instance, even to achieve success probability 2-Ω(n). We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by the generalized discrepancy method, the strongest technique in that model. We prove that quantum query complexity obeys an SDPT whenever the query lower bound for a single instance is proved by the polynomial method, one of the two main techniques in that model. In both models, we prove the corresponding XOR lemmas and threshold direct product theorems.

We develop a novel technique for communication lower bounds, the pattern matrix method. Specifically, fix an arbitrary function $f: \{0,1\}^n \to\{0,1\}$, and let $A_f$ be the matrix whose columns are each an application of f to some subset of the variables $x_1,x_2,\ldots,x_{4n}.$ We prove that $A_f$ has bounded-error communication complexity $\Omega(d),$ where d is the approximate degree of $f.$ This result remains valid in the quantum model, regardless of prior entanglement. In particular, it gives a new and simple proof of Razborov's breakthrough quantum lower bounds for disjointness and other symmetric predicates. We further characterize the discrepancy, approximate rank, and approximate trace norm of $A_f$ in terms of well-studied analytic properties of $f,$ broadly generalizing several recent results on small-bias communication and agnostic learning. The method of this paper has also enabled important progress in multiparty communication complexity.

We solve an open problem in communication complexity posed by Kushilevitz and Nisan (1997). Let Repsiv(f) and Dmuepsiv(f) denote the randomized and mu-distributional communication complexities off, respectively (e a small constant). Yao's well-known minimax principle states that Repsiv(f) = maxmu{Dmuepsiv(f)}. Kushilevitz and Nisan (1997) ask whether this equality is approximately preserved if the maximization is taken over product distributions only, rather than all distributions mu. We give a strong negative answer to this question. Specifically, we prove the existence of a function f : {0,1}nX {0,1}nrarr {0, 1}for which Repsiv(f) = Omega(n) but maxmuproduct{Dmuepsiv(f)} = 0(1).

The sign-rank of a matrix $A=[A_{ij}]$ with $\pm1$ entries is the least rank of a real matrix $B=[B_{ij}]$ with $A_{ij}B_{ij}>0$ for all $i,j$. We obtain the first exponential lower bound on the sign-rank of a function in $\mathsf{AC}^0$. Namely, let $f(x,y)=\bigwedge_{i=1,\dots,m}\bigvee_{j=1,\dots,m^2}(x_{ij}\wedge y_{ij})$. We show that the matrix $[f(x,y)]_{x,y}$ has sign-rank $\exp(\Omega(m))$. This in particular implies that $\Sigma_2^{cc}\not\subseteq\mathsf{UPP}^{cc}$, which solves a longstanding open problem in communication complexity posed by Babai, Frankl, and Simon [Proceedings of the 27th Symposium on Foundations of Computer Science (FOCS), 1986, pp. 337–347]. Our result additionally implies a lower bound in learning theory. Specifically, let $\phi_1,\dots,\phi_r:\{0,1\}^n\to\mathbb{R}$ be functions such that every DNF formula $f:\{0,1\}^n\to\{-1,+1\}$ of polynomial size has the representation $f\equiv\mathrm{sgn}(a_1\phi_1+\dots+a_r\phi_r)$ for some reals $a_1,\dots,a_r$. We prove that then $r\geqslant\exp(\Omega(n^{1/3}))$, which essentially matches an upper bound of $\exp(\tilde{O}(n^{1/3}))$, due to Klivans and Servedio [J. Comput. System Sci., 68 (2004), pp. 303–318]. Finally, our work yields the first exponential lower bound on the size of threshold-of-majority circuits computing a function in $\mathsf{AC}^0$. This substantially generalizes and strengthens the results of Krause and Pudlák [Theoret. Comput. Sci., 174 (1997), pp. 137–156].

The threshold degree of a Boolean function f: {0, 1}n¿ {-1, +1} is the least degree of a real polynomial p such f(x) ¿ sgn p(x). We construct two halfspaces on {0,1}nwhose intersection has threshold degree ¿(¿(n)), an exponential improvement on previous lower bounds. This solves an open problem due to Klivans (2002) and rules out the use of perceptronbased 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 ¿(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 Boolean functions f and g, the intersection f(x) ¿ g(y) has threshold degree O(d) if and only if ¿f - F||¿+ ||g - G||¿1, ..., fn). Essentially the only previous technique for analyzing the threshold degree was symmetrization (1969).

Let $$A_{1}, \ldots, A_{n}$$ be events in a probability space. The approximate inclusion-exclusion problem, due to Linial and Nisan (1990), is to estimate $${\bf P} [A_{1} \cup \ldots \cup A_{n}]$$ given $${\bf P} [\bigcap_{i\in S} A_{i}]$$ for |S| ≤ k. Kahn et al. (1996) solved this problem optimally for each k. We study the following more general question: estimate $${\bf P} [f(A_{1}, \ldots, A_{n})]$$ given $${\bf P} [\bigcap_{i\in S} A_{i}]$$ for |S| ≤ k, where f : {0, 1} n → {0, 1} is a given symmetric function. We solve this general problem for every f and k, giving an algorithm that runs in polynomial time and achieves an approximation error that is essentially optimal. We prove this optimal error to be $$2^{-\tilde\Theta(k^{2}/n)}$$ for k above a certain threshold, and $$\Theta(1)$$ otherwise. As part of our solution, we analyze, for every nonconstant symmetric f : {0, 1} n → {0, 1} and every $$\epsilon \in [2^{-n}, 1/3]$$ , the least degree $${\rm deg}_{\epsilon}(f)$$ of a polynomial that approximates f pointwise within $$\epsilon$$ . We show that $${\rm deg}_{\epsilon}(f) = \tilde\Theta({\rm deg}_{1/3}(f) + \sqrt{n {\rm log}(1/\epsilon))}$$ , where deg1/3(f) is well-known for each f. Previously, the answer for vanishing $$\epsilon$$ was known only for f = OR. We construct the approximating polynomial explicitly for all f and $$\epsilon$$ .

We construct a function in ${AC}^0$ that cannot be computed by a depth-2 majority circuit of size less than $\exp(\Theta(n^{1/5}))$. This solves an open problem due to Krause and Pudlák [Theoret. Comput. Sci., 174 (1997), pp. 137–156] and matches Allender's classic result [A note on the power of threshold circuits, in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Research Triangle Park, NC, 1989, pp. 580–584] that ${AC}^0$ can be efficiently simulated by depth-3 majority circuits. To obtain our result, we develop a novel technique for proving lower bounds on communication complexity. This technique, the Degree/Discrepancy Theorem, is of independent interest. It translates lower bounds on the threshold degree of any Boolean function into upper bounds on the discrepancy of a related function. Upper bounds on the discrepancy, in turn, immediately imply lower bounds on communication and circuit size. In particular, we exhibit the first known function in ${AC}^0$ with exponentially small discrepancy, $\exp(-\Omega(n^{1/5}))$, thereby establishing the separations $\Sigma_2^{cc}\not\subseteq{PP}^{cc}$ and $\Pi_2^{cc}\not\subseteq{PP}^{cc}$ in communication complexity.

The sign-rank of a matrix A = [Aij] with plusmn1 entries is the least rank of a real matrix B = [Bij] with AijBij> 0 for all i, j. We obtain the first exponential lower bound on the sign-rank of a function in AC0. Namely, let f(x, y) = Lambdai=1mLambdaj=1m2(xijLambda yij). We show that the matrix [f(x, y)]x,yhas sign-rank 2Omega(m). This in particular implies that Sigma2ccnsubeUPPcc, which solves a long-standing open problem posed by Babai, Frankl, and Simon (1986). Our result additionally implies a lower bound in learning theory. Specifically, let Phi1,..., Phir: {0, 1}nrarrRopf be functions such that every DNF formula f : {0, 1}nrarr {-1, +1} of polynomial size has the representation f equiv sign(a1Phi1+ hellip + arPhir) for some reals a1,..., ar. We prove that then r ges 2Omega(n1/3), which essentially matches an upper bound of 2Otilde(n1/3)due to Klivans and Servedio (2001). Finally, our work yields the first exponential lower bound on the size of threshold-of-majority circuits computing a function in AC0. This substantially generalizes and strengthens the results of Krause and Pudlak (1997).

In a breakthrough result, Razborov (2003) gave optimal lower bounds on the communication complexity of every function f of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in the bounded-error quantum model with and without prior entanglement. This was proved by the multidimensional discrepancy method. We give an entirely different proof of Razborov's result, using the original, one-dimensional discrepancy method. This refutes the commonly held intuition (Razborov 2003) that the original discrepancy method fails for functions such as DISJOINTNESS. More importantly, our communication lower bounds hold for a much broader class of functions for which no methods were available. Namely, fix an arbitrary function f:{0,1}n/4->{0,1} and let A be the Boolean matrix whose columns are each an application of f to some subset of the variables x1,x2,...,xn. We prove that the communication complexity of A in the bounded-error quantum model with and without prior entanglement is Omega(d), where d is the approximate degree of f. From this result, Razborov's lower bounds follow easily. Our result also establishes a large new class of total Boolean functions whose quantum communication complexity (regardless of prior entanglement) is at best polynomially smaller than their classical complexity. Our proof method is a novel combination of two ingredients. The first is a certain equivalence of approximation and orthogonality in Euclidean n-space, which follows by linear-programming duality. The second is a new construction of suitably structured matrices with low spectral norm, the pattern matrices, which we realize using matrix analysis and the Fourier transform over (Z2)n. The method of this paper has recently inspired important progress in multiparty communication complexity.

A halfspace matrix is a Boolean matrix A with rows indexed by linear threshold functions f , columns indexed by inputs x isin {-1,1}n, and the entries given by Af,x= f (x). We demonstrate the potential of halfspace matrices as tools to answer nontrivial open questions. (1) (Communication complexity) We exhibit a Boolean function f with discrepancy Omega(1/n4) under every product distribution but O(radicn /2n/4}) under a certain non-product distribution. This partially solves an open problem of Kushilevitz and Nisan. (2) (Complexity of sign matrices) We construct a matrix A isin {-1,1}NtimesNlogNwith dimension complexity logN but margin complexity Omega(N1/4/radic{log N}). This gap is an exponential improvement over previous work. As an application to circuit complexity, we prove an Omega(2n/4/(dradicn)) circuit lower bound for computing halfspaces by a majority of an arbitrary set of d gates. This complements a result of Goldmann, Hastad, and Razborov. In addition, we prove new results on the complexity measures of sign matrices, complementing recent work by Linial et al.(3) (Learning theory) We give a short and simple proof that the statistical-query (SQ) dimension of halfspaces in n dimensions is less than 2(n+1)2under all distributions (with n+1 being a trivial lower bound). This improves on the nO(1)estimate from the fundamental paper of Blum et al. Finally, we motivate our learning-theoretic result for the complexity community by showing that SQ dimension estimates for natural classes of Boolean functions can resolve major open problems in complexity theory. Specifically, we show that an exp(2(logn)o(1)) upper bound on the SQ dimension of AC0would imply an explicit language in PSPACEcc\PHcc.

We prove that AC0 cannot be efficiently simulated by MAJºMAJ circuits. Namely, we construct an AC0 circuit of depth 3 that requires MAJºMAJ circuits of size 2Ω(n1/5). This matches Allender's classic result that AC0 can be simulated by MAJºMAJºMAJ circuits of quasipolynomial size.

We give the first representation-independent hardness results for PAC learning intersections of halfspaces, a central concept class in computational learning theory. Our hardness results are derived from two public-key cryptosystems due to Regev, which are based on the worst-case hardness of well-studied lattice problems. Specifically, we prove that a polynomial-time algorithm for PAC learning intersections of nepsihalfspaces (for a constant epsi > 0) in n dimensions would yield a polynomial-time solution to Otilde(n1.5)-uSVP (unique shortest vector problem). We also prove that PAC learning intersections of nepsilow-weight half-spaces would yield a polynomial-time quantum solution to Otilde(n1.5)-SVP and Otilde(n1.5)-SIVP (shortest vector problem and shortest independent vector problem, respectively). By making stronger assumptions about the hardness of uSVP, SVP, and SIVP, we show that there is no polynomial-time algorithm for learning intersections of logcn halfspaces in n dimensions, for c > 0 sufficiently large. Our approach also yields the first representation-independent hardness results for learning polynomial-size depth-2 neural networks and polynomial-size depth-3 arithmetic circuits

DisViz is a visualization tool designed to assist students in learning graph algorithms, an important topic in the undergraduate curriculum. DisViz is intended for collaborative use by a group of students over a classroom network. This visualization system views network hosts as graph nodes and the socket connections among them, as graph edges. In typical usage, every student runs a copy of DisViz on his/her local machine. These applications detect each other's presence on the network and coordinate their actions to execute the graph algorithm in question and to deliver identical animations to every terminal.

A crucial part of the Computer Organization course is the design and analysis of hardware circuits. To teach this part of the course efficiently and to involve the entire class in the design of circuits, we have designed the SCAN system. Starting with a textual specification of a circuit, SCAN generates Java classes that can be used to simulate the way the circuit works. These circuits can be simulated locally or can join with other circuits to simulate larger machine function over a network. This paper describes the SCAN system, the Java classes it generates, and the way we use this in the Computer Organization class.