Boosting is a fundamental technique for generically improving the accuracy of learning algorithms (Schapire 1989). Existing boosting algorithms construct a strong learner using $O(\log(\frac{1}{\epsilon})/\gamma^2)$ calls to a $\gamma$-advantage weak learner, and this round complexity is known to be optimal for generic boosters that succeed on all concept classes (Freund 1995). We show that this lower bound can be circumvented for concept classes that satisfy a mild closure property. Specifically, we present a new boosting algorithm that, for any class $\mathcal{F}$ closed under $O(\log \frac{1}{\gamma})$-\textsc{Xor}, strong learns $\mathcal{F}$ using $O(\log \frac{1}{\epsilon})$ calls to a $\gamma$-advantage weak learner and a single batch of $\Tilde{O}(\log(\frac{1}{\epsilon})/\gamma^2)$ additional samples. Our algorithm arises from a new and simple connection between boosting and list-decodable codes. Viewing the target function as a message, we run the weak learner on its encoding and view the resulting weak hypothesis as a corrupted codeword. Feeding this corrupted codeword to a list decoder, we obtain a small list of candidate hypotheses, at least one of which is a strong hypothesis for the original function. Using additional samples, we identify and output this strong hypothesis.

The standard definition of PAC learning (Valiant 1984) requires learners to succeed under all distributions - even ones that are intractable to sample from. This stands in contrast to samplable PAC learning (Blum, Furst, Kearns, and Lipton 1993), where learners only have to succeed under samplable distributions. We study this distinction and show that samplable PAC substantially expands the power of efficient learners. We first construct a concept class that requires exponential sample complexity in standard PAC but is learnable with polynomial sample complexity in samplable PAC. We then lift this statistical separation to the computational setting and obtain a separation relative to a random oracle. Our proofs center around a new complexity primitive, explicit evasive sets, that we introduce and study. These are sets for which membership is easy to determine but are extremely hard to sample from. Our results extend to the online setting to similarly show that its landscape changes when the adversary is assumed to be efficient instead of computationally unbounded.

The apparent difficulty of efficient distribution-free PAC learning has led to a large body of work on distribution-specific learning. Distributional assumptions facilitate the design of efficient algorithms but also limit their reach and relevance. Towards addressing this, we prove a {\sl distributional-lifting theorem}: This upgrades a learner that succeeds with respect to a limited distribution family $\mathcal{D}$ to one that succeeds with respect to {\sl any} distribution $D^\star$, with an efficiency overhead that scales with the complexity of expressing $D^\star$ as a mixture of distributions in $\mathcal{D}$. Recent work of Blanc, Lange, Malik, and Tan considered the special case of lifting uniform-distribution learners and designed a lifter that uses a conditional sample oracle for $D^\star$, a strong form of access not afforded by the standard PAC model. Their approach, which draws on ideas from semi-supervised learning, first learns $D^\star$ and then uses this information to lift. We show that their approach is information-theoretically intractable with access only to random examples, thereby giving formal justification for their use of the conditional sample oracle. We then take a different approach that sidesteps the need to learn $D^\star$, yielding a lifter that works in the standard PAC model and enjoys additional advantages: it works for all base distribution families, preserves the noise tolerance of learners, has better sample complexity, and is simpler.

A central question in computer science and statistics is whether efficient algorithms can achieve the information-theoretic limits of statistical problems. Many computational-statistical tradeoffs have been shown under average-case assumptions, but since statistical problems are average-case in nature, it has been a challenge to base them on standard worst-case assumptions.In PAC learning where such tradeoffs were first studied, the question is whether computational efficiency can come at the cost of using more samples than informationtheoretically necessary. We base such tradeoffs on NP-hardness and obtain:◦ Sharp computational-statistical tradeoffs assuming NP requires exponential time: For every polynomial $p(n)$, there is an n-variate class $\mathcal{C}$ with VC dimension 1 such that the sample complexity of time-efficiently learning $\mathcal{C}$ is $\Theta(p(n))$.◦ A characterization of RP vs. NP in terms of learning: RP = NP iff every NP-enumerable class is learnable with $O(\operatorname{VCdim}(\mathcal{C}))$ samples in polynomial time. The forward implication has been known since (Pitt and Valiant, 1988); we prove the reverse implication.Notably, all our lower bounds hold against improper learners. These are the first NP-hardness results for improperly learning a subclass of polynomial-size circuits, circumventing formal barriers of Applebaum, Barak, and Xiao (2008).

We consider the task of properly PAC learning decision trees with queries. Recent work of Koch, Strassle, and Tan showed that the strictest version of this task, where the hypothesis tree T is required to be optimally small, is NP-hard. Their work leaves open the question of whether the task remains intractable if T is only required to be close to optimal, say within a factor of 2, rather than exactly optimal. We answer this affirmatively and show that the task indeed remains NP-hard even if T is allowed to be within any constant factor of optimal. More generally, our result allows for a smooth tradeoff between the hardness assumption and inapproximability factor. As Koch et al.’s techniques do not appear to be amenable to such a strengthening, we first recover their result with a new and simpler proof, which we couple with a new XOR lemma for decision trees. While there is a large body of work on XOR lemmas for decision trees, our setting necessitates parameters that are extremely sharp and are not known to be attainable by existing such lemmas. Our work also carries new implications for the related problem of Decision Tree Minimization.

We connect the problem of properly PAC learning decision trees to the parameterized Nearest Codeword Problem (k-NCP). Despite significant effort by the respective communities, algorithmic progress on both problems has been stuck: the fastest known algorithm for the former runs in quasipolynomial time (Ehrenfeucht and Haussler 1989) and the best known approximation ratio for the latter is$O$($n$/logn) (Berman and Karpinsky 2002; Alon, Panigrahy, and Yekhanin 2009). Research on both problems has thus far proceeded independently with no known connections. We show that any improvement of Ehrenfeucht and Haussler's algorithm will yield$O$(logn)-approximation algorithms for k-NCP, an exponential improvement of the current state of the art. This can be interpreted either as a new avenue for designing algorithms for k-NCP, or as one for establishing the optimality of Ehrenfeucht and Haussler's algorithm. Furthermore, our reduction along with existing inapproximability results for k - NCP already rule out polynomial-time algorithms for properly learning decision trees. A notable aspect of our hardness results is that they hold even in the setting of weak learning whereas prior ones were limited to the setting of strong learning.

Smooth boosters generate distributions that do not place too much weight on any given example. Originally introduced for their noise-tolerant properties, such boosters have also found applications in differential privacy, reproducibility, and quantum learning theory. We study and settle the sample complexity of smooth boosting: we exhibit a class that can be weak learned to$\gamma$. -advantage over smooth distributions with$m$samples, for which strong learning over the uniform distribution requires$\tilde{\Omega}(1/\gamma^{2}{)}\cdot m$, samples. This matches the overhead of existing smooth boosters and provides the first separation from the setting of distribution-independent boosting, for which the corresponding overhead is$O(1/\gamma)$. Our work also sheds new light on Impagliazzo's hardcore theorem from complexity theory, all known proofs of which can be cast in the framework of smooth boosting. For a function$f$that is mildly hard against size-s circuits, the hardcore theorem provides a set of inputs on which$f$is extremely hard against size-$s^{\prime}$circuits. A downside of this important result is the loss in circuit size, i.e. that$s^{\prime}\ll s$. Answering a question of Trevisan, we show that this size loss is necessary and in fact, the parameters achieved by known proofs are the best possible.

We investigate the computational efficiency of multitask learning of Boolean functions over the $d$-dimensional hypercube, that are related by means of a feature representation of size $k\ll d$ shared across all tasks. We present a polynomial time multitask learning algorithm for the concept class of halfspaces with margin $\gamma$, which is based on a simultaneous boosting technique and requires only $\mathrm{poly}(k/\gamma)$ samples-per-task and $\mathrm{poly}(k\log(d)/\gamma)$ samples in total. In addition, we prove a computational separation, showing that assuming there exists a concept class that cannot be learned in the attribute-efficient model, we can construct another concept class such that can be learned in the attribute-efficient model, but cannot be multitask learned efficiently—multitask learning this concept class either requires super-polynomial time complexity or a much larger total number of samples.

We prove a strong composition theorem for junta complexity and show how such theorems can be used to generically boost the performance of property testers.The $\varepsilon$-approximate junta complexity of a function f is the smallest integer r such that f is $\varepsilon$-close to a function that depends only on r variables. A strong composition theorem states that if f has large $\varepsilon$-approximate junta complexity, then $g \circ f$ has even larger $\varepsilon^{\prime}$-approximate junta complexity, even for $\varepsilon^{\prime} \gg \varepsilon$. We develop a fairly complete understanding of this behavior, proving that the junta complexity of $g \circ f$ is characterized by that of f along with the multivariate noise sensitivity of g. For the important case of symmetric functions g, we relate their multivariate noise sensitivity to the simpler and well-studied case of univariate noise sensitivity.We then show how strong composition theorems yield boosting algorithms for property testers: with a strong composition theorem for any class of functions, a large-distance tester for that class is immediately upgraded into one for small distances. Combining our contributions yields a booster for junta testers, and with it new implications for junta testing. This is the first boosting-type result in property testing, and we hope that the connection to composition theorems adds compelling motivation to the study of both topics.

We prove that it is NP-hard to properly PAC learn decision trees with queries, resolving a longstanding open problem in learning theory (Bshouty 1993; Guijarro–Lavín–Raghavan 1999; Mehta–Raghavan 2002; Feldman 2016). While there has been a long line of work, dating back to (Pitt–Valiant 1988), establishing the hardness of properly learning decision trees from random examples, the more challenging setting of query learners necessitates different techniques and there were no previous lower bounds. En route to our main result, we simplify and strengthen the best known lower bounds for a different problem of Decision Tree Minimization (Zantema—Bodlaender 2000; Sieling 2003).On a technical level, we introduce the notion of hardness distillation, which we study for decision tree complexity but can be considered for any complexity measure: for a function that requires large decision trees, we give a general method for identifying a small set of inputs that is responsible for its complexity. Our technique even rules out query learners that are allowed constant error. This contrasts with existing lower bounds for the setting of random examples which only hold for inverse-polynomial error.Our result, taken together with a recent almost-polynomial time query algorithm for properly learning decision trees under the uniform distribution (Blanc–Lange–Qiao–Tan 2022), demonstrates the dramatic impact of distributional assumptions on the problem.

In the certification problem, the algorithm is given a function $f$ with certificate complexity $k$ and an input $x^\star$, and the goal is to find a certificate of size $\le \text{poly}(k)$ for $f$'s value at $x^\star$. This problem is in $\mathsf{NP}^{\mathsf{NP}}$, and assuming $\mathsf{P} \ne \mathsf{NP}$, is not in $\mathsf{P}$. Prior works, dating back to Valiant in 1984, have therefore sought to design efficient algorithms by imposing assumptions on $f$ such as monotonicity. Our first result is a $\mathsf{BPP}^{\mathsf{NP}}$ algorithm for the general problem. The key ingredient is a new notion of the balanced influence of variables, a natural variant of influence that corrects for the bias of the function. Balanced influences can be accurately estimated via uniform generation, and classic $\mathsf{BPP}^{\mathsf{NP}}$ algorithms are known for the latter task. We then consider certification with stricter instance-wise guarantees: for each $x^\star$, find a certificate whose size scales with that of the smallest certificate for $x^\star$. In sharp contrast with our first result, we show that this problem is $\mathsf{NP}^{\mathsf{NP}}$-hard even to approximate. We obtain an optimal inapproximability ratio, adding to a small handful of problems in the higher levels of the polynomial hierarchy for which optimal inapproximability is known. Our proof involves the novel use of bit-fixing dispersers for gap amplification.

We propose a simple generalization of standard and empirically successful decision tree learning algorithms such as ID3, C4.5, and CART. These algorithms, which have been central to machine learning for decades, are greedy in nature: they grow a decision tree by iteratively splitting on the best attribute. Our algorithm, Top-$k$, considers the $k$ best attributes as possible splits instead of just the single best attribute. We demonstrate, theoretically and empirically, the power of this simple generalization. We first prove a greediness hierarchy theorem showing that for every $k\in \mathbb{N}$, Top-$(k+1)$ can be dramatically more powerful than Top-$k$: there are data distributions for which the former achieves accuracy $1-\epsilon$, whereas the latter only achieves accuracy $\frac{1}{2}+\epsilon$. We then show, through extensive experiments, that Top-$k$ outperforms the two main approaches to decision tree learning: classic greedy algorithms and more recent ``optimal decision tree'' algorithms. On one hand, Top-$k$ consistently enjoys significant accuracy gains over greedy algorithms across a wide range of benchmarks. On the other hand, Top-$k$ is markedly more scalable than optimal decision tree algorithms and is able to handle dataset and feature set sizes that remain far beyond the reach of these algorithms. The code to reproduce our results is available at https://github.com/SullivanC19/pydl8.5-topk.

We study correlation clustering in the streaming setting. This problem has been studied extensively and numerous algorithms have been developed, most requiring multiple passes over the stream. For the important case of single-pass algorithms, recent work of Assadi and Wang [8] obtains a c-approximation using Õ(n) space where c > 105 is a constant and n is the number of vertices to be clustered. We present a single-pass algorithm that obtains a 5-approximation using O(n) space. The algorithm itself is extremely simple and has implications beyond the streaming setting (such as for dynamic and local computation algorithms). The approximation analysis, on the other hand, is delicate and in fact tight.

We establish new hardness results for decision tree optimization problems, adding to a line of work that dates back to Hyafil and Rivest in 1976. We prove, under the randomized exponential time hypothesis, superpolynomial runtime lower bounds for two basic problems: given an explicit representation of a function f and a generator for a distribution D

We show how any PAC learning algorithm that works under the uniform distribution can be transformed, in a blackbox fashion, into one that works under an arbitrary and unknown distribution ‍D. The efficiency of our transformation scales with the inherent complexity of ‍D, running in (n, (md)d) time for distributions over n whose pmfs are computed by depth-d decision trees, where m is the sample complexity of the original algorithm. For monotone distributions our transformation uses only samples from ‍D, and for general ones it uses subcube conditioning samples.

We study the complexity of computing majority as a composition of local functions: Maj_n = h(g_1,…,g_m), where each g_j: {0,1}ⁿ → {0,1} is an arbitrary function that queries only k ≪ n variables and h: {0,1}^m → {0,1} is an arbitrary combining function. We prove an optimal lower bound of m ≥ Ω(n/k log k) on the number of functions needed, which is a factor Ω(log k) larger than the ideal m = n/k. We call this factor the composition overhead; previously, no superconstant lower bounds on it were known for majority. Our lower bound recovers, as a corollary and via an entirely different proof, the best known lower bound for bounded-width branching programs for majority (Alon and Maass '86, Babai et al. '90). It is also the first step in a plan that we propose for breaking a longstanding barrier in lower bounds for small-depth boolean circuits. Novel aspects of our proof include sharp bounds on the information lost as computation flows through the inner functions g_j, and the bootstrapping of lower bounds for a multi-output function (Hamming weight) into lower bounds for a single-output one (majority).

We initiate the study of a fundamental question concerning adversarial noise models in statistical problems where the algorithm receives i.i.d. draws from a distribution $\mathcal{D}$. The definitions of these adversaries specify the {\sl type} of allowable corruptions (noise model) as well as {\sl when} these corruptions can be made (adaptivity); the latter differentiates between oblivious adversaries that can only corrupt the distribution $\mathcal{D}$ and adaptive adversaries that can have their corruptions depend on the specific sample $S$ that is drawn from $\mathcal{D}$. We investigate whether oblivious adversaries are effectively equivalent to adaptive adversaries, across all noise models studied in the literature, under a unifying framework that we introduce. Specifically, can the behavior of an algorithm $\mathcal{A}$ in the presence of oblivious adversaries always be well-approximated by that of an algorithm $\mathcal{A}’$ in the presence of adaptive adversaries? Our first result shows that this is indeed the case for the broad class of {\sl statistical query} algorithms, under all reasonable noise models. We then show that in the specific case of {\sl additive noise}, this equivalence holds for {\sl all} algorithms. Finally, we map out an approach towards proving this statement in its fullest generality, for all algorithms and under all reasonable noise models.

We study parallel algorithms for correlation clustering. Each pair among n objects is labeled as either “similar” or “dissimilar”. The goal is to partition the objects into arbitrarily many clusters while minimizing the number of disagreements with the labels.Our main result is an algorithm that for any $\varepsilon>0$ obtains a (3 + $\varepsilon$)-approximation in $O(1/\varepsilon$) rounds (of models such as massively parallel computation, local, and semi-streaming). This is a culminating point for the rich literature on parallel correlation clustering. On the one hand, the approximation (almost) matches a natural barrier of 3 for combinatorial algorithms. On the other hand, the algorithm’s round-complexity is essentially constant.To achieve this result, we introduce a simple $O(1/\varepsilon$)-round parallel algorithm. Our main result is to provide an analysis of this algorithm, showing that it achieves a (3 + $\varepsilon$)-approximation. Our analysis draws on new connections to sublinear-time algorithms. Specifically, it builds on the work of Yoshida, Yamamoto, and Ito [1] on bounding the “query complexity” of greedy maximal independent set. To our knowledge, this is the first application of this method in analyzing the approximation ratio of any algorithm.Full version. Due to the page limit, this version of the paper does not include all the proofs. The full version of the paper is available at [2].

We give the first reconstruction algorithm for decision trees: given queries to a function f that is opt-close to a size-s decision tree, our algorithm provides query access to a decision tree T where: - T has size S := s^O((log s)²/ε³); - dist(f,T) ≤ O(opt)+ε; - Every query to T is answered with poly((log s)/ε)⋅ log n queries to f and in poly((log s)/ε)⋅ n log n time. This yields a tolerant tester that distinguishes functions that are close to size-s decision trees from those that are far from size-S decision trees. The polylogarithmic dependence on s in the efficiency of our tester is exponentially smaller than that of existing testers. Since decision tree complexity is well known to be related to numerous other boolean function properties, our results also provide a new algorithm for reconstructing and testing these properties.

We design an algorithm for finding counterfactuals with strong theoretical guarantees on its performance. For any monotone model $f : X^d \to \{0,1\}$ and instance $x^\star$, our algorithm makes \[{S}(f)^{O(\Delta_f(x^\star))}\cdot \log d\]{queries} to $f$ and returns an {\sl optimal} counterfactual for $x^\star$: a nearest instance $x’$ to $x^\star$ for which $f(x’)\ne f(x^\star)$. Here $S(f)$ is the sensitivity of $f$, a discrete analogue of the Lipschitz constant, and $\Delta_f(x^\star)$ is the distance from $x^\star$ to its nearest counterfactuals. The previous best known query complexity was $d^{\,O(\Delta_f(x^\star))}$, achievable by brute-force local search. We further prove a lower bound of $S(f)^{\Omega(\Delta_f(x^\star))} + \Omega(\log d)$ on the query complexity of any algorithm, thereby showing that the guarantees of our algorithm are essentially optimal.

Using the framework of boosting, we prove that all impurity-based decision tree learning algorithms, including the classic ID3, C4.5, and CART, are highly noise tolerant. Our guarantees hold under the strongest noise model of nasty noise, and we provide near-matching upper and lower bounds on the allowable noise rate. We further show that these algorithms, which are simple and have long been central to everyday machine learning, enjoy provable guarantees in the noisy setting that are unmatched by existing algorithms in the theoretical literature on decision tree learning. Taken together, our results add to an ongoing line of research that seeks to place the empirical success of these practical decision tree algorithms on firm theoretical footing.

We study the problem of certification: given queries to a function f : {0,1}n → {0,1} with certificate complexity ≤ k and an input x⋆, output a size-k certificate for f’s value on x⋆.

We give an n O (log log n ) -time membership query algorithm for properly and agnostically learning decision trees under the uniform distribution over { ± 1} n . Even in the realizable setting, the previous fastest runtime was n O (log n ) , a consequence of a classic algorithm of Ehrenfeucht and Haussler. Our algorithm shares similarities with practical heuristics for learning decision trees, which we augment with additional ideas to circumvent known lower bounds against these heuristics. To analyze our algorithm, we prove a new structural result for decision trees that strengthens a theorem of O’Donnell, Saks, Schramm, and Servedio. While the OSSS theorem says that every decision tree has an influential variable, we show how every decision tree can be “pruned” so that every variable in the resulting tree is influential.

We give a pseudorandom generator that fools m -facet polytopes over {0, 1} n with seed length polylog( m ) · log n . The previous best seed length had superlinear dependence on m .

Greedy decision tree learning heuristics are mainstays of machine learning practice, but theoretical justification for their empirical success remains elusive. In fact, it has long been known that there are simple target functions for which they fail badly (Kearns and Mansour, STOC 1996). Recent work of Brutzkus, Daniely, and Malach (COLT 2020) considered the smoothed analysis model as a possible avenue towards resolving this disconnect. Within the smoothed setting and for targets f that are k-juntas, they showed that these heuristics successfully learn f with depth-k decision tree hypotheses. They conjectured that the same guarantee holds more generally for targets that are depth-k decision trees. We provide a counterexample to this conjecture: we construct targets that are depth-k decision trees and show that even in the smoothed setting, these heuristics build trees of depth 2^{Ω(k)} before achieving high accuracy. We also show that the guarantees of Brutzkus et al. cannot extend to the agnostic setting: there are targets that are very close to k-juntas, for which these heuristics build trees of depth 2^{Ω(k)} before achieving high accuracy.

The Stabbing Planes proof system [Paul Beame et al., 2018] was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas - certain unsatisfiable systems of linear equations od 2 - which are canonical hard examples for many algebraic proof systems. In a recent (and surprising) result, Dadush and Tiwari [Daniel Dadush and Samarth Tiwari, 2020] showed that these short refutations of the Tseitin formulas could be translated into quasi-polynomial size and depth Cutting Planes proofs, refuting a long-standing conjecture. This translation raises several interesting questions. First, whether all Stabbing Planes proofs can be efficiently simulated by Cutting Planes. This would allow for the substantial analysis done on the Cutting Planes system to be lifted to practical mixed integer programming solvers. Second, whether the quasi-polynomial depth of these proofs is inherent to Cutting Planes. In this paper we make progress towards answering both of these questions. First, we show that any Stabbing Planes proof with bounded coefficients (SP*) can be translated into Cutting Planes. As a consequence of the known lower bounds for Cutting Planes, this establishes the first exponential lower bounds on SP*. Using this translation, we extend the result of Dadush and Tiwari to show that Cutting Planes has short refutations of any unsatisfiable system of linear equations over a finite field. Like the Cutting Planes proofs of Dadush and Tiwari, our refutations also incur a quasi-polynomial blow-up in depth, and we conjecture that this is inherent. As a step towards this conjecture, we develop a new geometric technique for proving lower bounds on the depth of Cutting Planes proofs. This allows us to establish the first lower bounds on the depth of Semantic Cutting Planes proofs of the Tseitin formulas.

We give an$n^{O(\log\log n)}$-time membership query algorithm for properly and agnostically learning decision trees under the uniform distribution over$\{\pm 1\}^{n}$. Even in the realizable setting, the previous fastest runtime was$n^{O(\log n)}$, a consequence of a classic algorithm of Ehrenfeucht and Haussler. Our algorithm shares similarities with practical heuristics for learning decision trees, which we augment with additional ideas to circumvent known lower bounds against these heuristics. To analyze our algorithm, we prove a new structural result for decision trees that strengthens a theorem of O'Donnell, Saks, Schramm, and Servedio. While the OSSS theorem says that every decision tree has an influential variable, we show how every decision tree can be “pruned” so that every variable in the resulting tree is influential.

In 1992 Mansour proved that every size-s DNF formula is Fourier-concentrated on$s^{O(\log\log s)}$coefficients. We improve this to$s^{O(\log\log k)}$where$k$is the read number of the DNF. Since$k$is always at most$s$, our bound matches Mansour's for all DNFs and strengthens it for small-read ones. The previous best bound for read-k DNFs was$s^{O(k^{3/2})}$. For$k$up to$\tilde{\Theta}$(log log$s$), we further improve our bound to the optimal poly$(s)$; previously no such bound was known for any$k=\omega_{s}(1)$. Our techniques involve new connections between the term structure of a DNF, viewed as a set system, and its Fourier spectrum. The full version of this paper is available at https://arxiv.org/abs/2109.04525. We strongly recommend reading the full version because it has better typesetting.

We study the complexity of small-depth Frege proofs and give the first tradeoffs between the size of each line and the number of lines. Existing lower bounds apply to the overall proof size-the sum of sizes of all lines-and do not distinguish between these notions of complexity. For depth-d Frege proofs of the Tseitin principle where each line is a size-s formula, we prove that$\exp(n/2^{\Omega(d\sqrt{\log s})})$many lines are necessary. This yields new lower bounds on line complexity that are not implied by$\mathbf{H}\mathop{\mathbf{a}}\!\!\!\!^{\circ}\mathbf{stad}$'s recent$\exp(n^{\Omega(1/d)})$lower bound on the overall proof size. For$s$= poly$(n)$, for example, our lower bound remains$\exp(n^{1-o(1)})$for all$d=o(\sqrt{\log n})$, whereas$\mathbf{H}\mathop{\mathbf{a}}\!\!\!\!^{\circ}\mathbf{stad}$'s lower bound is$\exp(n^{o(1)})$once$d\ = \omega_{n}(1)$. Our main conceptual contribution is the simple obser-vation that techniques for establishing correlation bounds in circuit complexity can be leveraged to establish such tradeoffs in proof complexity.

We consider the problem of explaining the predictions of an arbitrary blackbox model $f$: given query access to $f$ and an instance $x$, output a small set of $x$'s features that in conjunction essentially determines $f(x)$. We design an efficient algorithm with provable guarantees on the succinctness and precision of the explanations that it returns. Prior algorithms were either efficient but lacked such guarantees, or achieved such guarantees but were inefficient. We obtain our algorithm via a connection to the problem of {\sl implicitly} learning decision trees. The implicit nature of this learning task allows for efficient algorithms even when the complexity of~$f$ necessitates an intractably large surrogate decision tree. We solve the implicit learning problem by bringing together techniques from learning theory, local computation algorithms, and complexity theory. Our approach of “explaining by implicit learning” shares elements of two previously disparate methods for post-hoc explanations, global and local explanations, and we make the case that it enjoys advantages of both.

We give a randomness-efficient Massively Parallel Computation (MPC) algorithm for deciding whether an undirected graph is connected. For Connectivity on n-vertex, m-edge graphs whose components have diameter at most D = 2o(log n/ log log n), our algorithm runs in R = O(log D + log logm/n,.n) rounds and uses a total of (log n)O(R) random bits, O(m) machines, and n1-Ω(1) space per machine with good probability.1 With good probability means with probability at least 1 - 1/poly ((m log n)/n), which is the same as in Liu, Tarjan, and Zhong (SPAA '20). Our algorithm achieves a super-polynomial saving in randomness complexity as compared to the breakthrough algorithm of Andoni et al. (FOCS '18) and the subsequent improvement by Behnezhad et al. (FOCS '19). Our algorithm has the same round complexity as that of Behnezhad et al., but uses more total space.

We consider the problem of designing query strategies for priced information, introduced by Charikar et al. In this problem the algorithm designer is given a function f : {0, 1}n → {±1} and a price associated with each of the n coordinates. The goal is to design a query strategy for determining f's value on unknown inputs for minimum cost. Prior works on this problem have focused on specific classes of functions. We analyze a simple and natural strategy that applies to all functions f, and show that its performance relative to the optimal strategy can be expressed in terms of a basic complexity measure of f, its influence. For ∊ ∊ (0, ½), writing opt to denote the expected cost of the optimal strategy that errs on at most an ∊-fraction of inputs, our strategy has expected cost opt · Inf(f)/∊2 and also errs on at most an O(∊)-fraction of inputs. This connection yields new guarantees that complement existing ones for a number of function classes that have been studied in this context, as well as new guarantees for new classes. Finally, we show that improving on the parameters that we achieve will require making progress on the longstanding open problem of properly learning decision trees.

The randomized query complexity 𝖱(f) of a boolean function f: {0,1}ⁿ → {0,1} is famously characterized (via Yao’s minimax) by the least number of queries needed to distinguish a distribution 𝒟₀ over 0-inputs from a distribution 𝒟₁ over 1-inputs, maximized over all pairs (𝒟₀,𝒟₁). We ask: Does this task become easier if we allow query access to infinitely many samples from either 𝒟₀ or 𝒟₁? We show the answer is no: There exists a hard pair (𝒟₀,𝒟₁) such that distinguishing 𝒟₀^∞ from 𝒟₁^∞ requires Θ(𝖱(f)) many queries. As an application, we show that for any composed function f∘g we have 𝖱(f∘g) ≥ Ω(fbs(f)𝖱(g)) where fbs denotes fractional block sensitivity.

We give strengthened provable guarantees on the performance of widely employed and empirically successful {\sl top-down decision tree learning heuristics}. While prior works have focused on the realizable setting, we consider the more realistic and challenging {\sl agnostic} setting. We show that for all monotone functions $f$ and $s\in \mathbb{N}$, these heuristics construct a decision tree of size $s^{\tilde{O}((\log s)/\varepsilon^2)}$ that achieves error $\le \mathsf{opt}_s + \varepsilon$, where $\mathsf{opt}_s$ denotes the error of the optimal size-$s$ decision tree for $f$. Previously such a guarantee was not known to be achievable by any algorithm, even one that is not based on top-down heuristics. We complement our algorithmic guarantee with a near-matching $s^{\tilde{\Omega}(\log s)}$ lower bound.

Consider the following heuristic for building a decision tree for a function f : {0,1}^n → {± 1}. Place the most influential variable x_i of f at the root, and recurse on the subfunctions f_{x_i=0} and f_{x_i=1} on the left and right subtrees respectively; terminate once the tree is an ε-approximation of f. We analyze the quality of this heuristic, obtaining near-matching upper and lower bounds: - Upper bound: For every f with decision tree size s and every ε ∈ (0,1/2), this heuristic builds a decision tree of size at most s^O(log(s/ε)log(1/ε)). - Lower bound: For every ε ∈ (0,1/2) and s ≤ 2^Õ(√n), there is an f with decision tree size s such that this heuristic builds a decision tree of size s^Ω~(log s). We also obtain upper and lower bounds for monotone functions: s^O(√{log s}/ε) and s^Ω(∜{log s}) respectively. The lower bound disproves conjectures of Fiat and Pechyony (2004) and Lee (2009). Our upper bounds yield new algorithms for properly learning decision trees under the uniform distribution. We show that these algorithms - which are motivated by widely employed and empirically successful top-down decision tree learning heuristics such as ID3, C4.5, and CART - achieve provable guarantees that compare favorably with those of the current fastest algorithm (Ehrenfeucht and Haussler, 1989), and even have certain qualitative advantages. Our lower bounds shed new light on the limitations of these heuristics. Finally, we revisit the classic work of Ehrenfeucht and Haussler. We extend it to give the first uniform-distribution proper learning algorithm that achieves polynomial sample and memory complexity, while matching its state-of-the-art quasipolynomial runtime.

We show that top-down decision tree learning heuristics (such as ID3, C4.5, and CART) are amenable to highly efficient {\sl learnability estimation}: for monotone target functions, the error of the decision tree hypothesis constructed by these heuristics can be estimated with {\sl polylogarithmically} many labeled examples, exponentially smaller than the number necessary to run these heuristics, and indeed, exponentially smaller than information-theoretic minimum required to learn a good decision tree. This adds to a small but growing list of fundamental learning algorithms that have been shown to be amenable to learnability estimation. En route to this result, we design and analyze sample-efficient {\sl minibatch} versions of top-down decision tree learning heuristics and show that they achieve the same provable guarantees as the full-batch versions. We further give ``active local'' versions of these heuristics: given a test point $x^\star$, we show how the label $T(x^\star)$ of the decision tree hypothesis $T$ can be computed with polylogarithmically many labeled examples, exponentially smaller than the number necessary to learn~$T$.

We propose a simple extension of {\sl top-down decision tree learning heuristics} such as ID3, C4.5, and CART. Our algorithm achieves provable guarantees for all target functions $f: \{-1,1\}^n \to \{-1,1\}$ with respect to the uniform distribution, circumventing impossibility results showing that existing heuristics fare poorly even for simple target functions. The crux of our extension is a new splitting criterion that takes into account the correlations between $f$ and {\sl small subsets} of its attributes. The splitting criteria of existing heuristics (e.g. Gini impurity and information gain), in contrast, are based solely on the correlations between $f$ and its {\sl individual} attributes. Our algorithm satisfies the following guarantee: for all target functions $f : \{-1,1\}^n \to \{-1,1\}$, sizes $s\in \N$, and error parameters $\eps$, it constructs a decision tree of size $s^{\tilde{O}((\log s)^2/\eps^2)}$ that achieves error $\le O(\opt_s) + \eps$, where $\opt_s$ denotes the error of the optimal size-$s$ decision tree for $f$. A key technical notion that drives our analysis is the {\sl noise stability} of $f$, a well-studied smoothness measure of $f$.

We consider unconditional lower bounds in the Adaptive Massively Parallel Computation (AMPC) model introduced by Behnezhad et al. (SPAA 19), which is an adaptive variant of the Massively Parallel Computation (MPC) model. Our first contribution is an optimal lower bound on the round complexity of distinguishing whether an input graph is a cycle of length n or two cycles of length n/2. This problem, 1v2-CIRCLE, has emerged as a central problem in the study of modern massively parallel computation. We prove that any AMPC algorithm for the 1v2-CIRCLE problem with I/O capacity O(nε) per machine requires Ω(1/ε) rounds, matching the upper bound of Behnezhad et al.

We give a pseudorandom generator that fools degree-d polynomial threshold functions over n-dimensional Gaussian space with seed length d O(logd) · logn. All previous generators had a seed length with at least a 2 d dependence on d.

The design of pseudorandom generators and deterministic approximate counting algorithms for DNF formulas are important challenges in unconditional derandomization. Numerous works on these problems have focused on the subclass of small-read DNF formulas, which are formulas in which each variable occurs a bounded number of times. Our first main result is a pseudorandom generator which ε-fools M-term read-k DNFs using seed length poly(k, log(1/ε))·log M + O(log n). This seed length is exponentially shorter, as a function of both k and 1/ε, than the best previous PRG for read-k DNFs. We also give a deterministic algorithm that approximates the number of satisfying assignments of an M-term read-k DNF to any desired (1 + ε)-multiplicative accuracy in time poly(n)·min {(M/ε)poly(k, log(k/ε)), (M/ε)Õ(log((k log M)/ε))}. For any constant k this is a PTAS, and our runtime remains almost-polynomial (M Õ(log log M)) for k as large as any polylog(M). Prior to our work, the fastest deterministic algorithm ran in time even for k = 2, and no PTAS was known for any non-trivial subclass of DNFs. The common essential ingredients in these pseudorandomness results are new analytic inequalities for read-k DNFs. These inequalities may be of independent interest and utility; as an example application, we use them to obtain a significant improvement on the previous state of the art for agnostically learning read-k DNFs.

We give a pseudorandom generator that fools m-facet polytopes over {0,1}n with seed length polylog(m) · log(n). The previous best seed length had superlinear dependence on m. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any {0,1}-integer program.

We give the best known pseudorandom generators for two touchstone classes in unconditional derandomization: an $\varepsilon$-PRG for the class of size-$M$ depth-$d$ $\mathsf{AC}^0$ circuits with seed length $\log(M)^{d+O(1)}\cdot \log(1/\varepsilon)$, and an $\varepsilon$-PRG for the class of $S$-sparse $\mathbb{F}_2$ polynomials with seed length $2^{O(\sqrt{\log S})}\cdot \log(1/\varepsilon)$. These results bring the state of the art for unconditional derandomization of these classes into sharp alignment with the state of the art for computational hardness for all parameter settings: improving on the seed lengths of either PRG would require breakthrough progress on longstanding and notorious circuit lower bounds. The key enabling ingredient in our approach is a new \emph{pseudorandom multi-switching lemma}. We derandomize recently-developed \emph{multi}-switching lemmas, which are powerful generalizations of Håstad's switching lemma that deal with \emph{families} of depth-two circuits. Our pseudorandom multi-switching lemma---a randomness-efficient algorithm for sampling restrictions that simultaneously simplify all circuits in a family---achieves the parameters obtained by the (full randomness) multi-switching lemmas of Impagliazzo, Matthews, and Paturi [IMP12] and Håstad [Hås14]. This optimality of our derandomization translates into the optimality (given current circuit lower bounds) of our PRGs for $\mathsf{AC}^0$ and sparse $\mathbb{F}_2$ polynomials.

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e. AC0tampering functions), our codes have codeword length n = k1+0(1)for a k-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay and Li (STOC 2017), which had codeword length 2O(√k). Our construction remains efficient for circuit depths as large as Θ(log(n)/loglog(n)) (indeed, our codeword length remains n ≤ k1+ε), and extending our result beyond this would require separating P from NC1. We obtain our codes via a new efficient non-malleable reduction from small-depth tampering to split-state tampering. A novel aspect of our work is the incorporation of techniques from unconditional derandomization into the framework of non-malleable reductions. In particular, a key ingredient in our analysis is a recent pseudorandom switching lemma of Trevisan and Xue (CCC 2013), a derandomization of the influential switching lemma from circuit complexity; the randomness-efficiency of this switching lemma translates into the rate-efficiency of our codes via our non-malleable reduction.

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function f :{0,1} n → {0,1} is a k -junta or ϵ-far from every k -junta must make Ω ˜ ( k 3/2 ) / ϵ) many queries for a wide range of parameters k and ϵ. Our result dramatically improves previous lower bounds and is essentially optimal since there is a known non-adaptive junta tester which makes Ω ˜ ( k 3/2 ) / ϵ queries. Combined with the known existence of an adaptive tester which makes O ( k log k + k /ϵ) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.

We give a poly(log(n),1/epsilon)-query adaptive algorithm for testing whether an unknown Boolean function f:{-1, 1}^n -> {-1, 1}, which is promised to be a halfspace, is monotone versus epsilon-far from monotone. Since non-adaptive algorithms are known to require almost Omega(n^{1/2}) queries to test whether an unknown halfspace is monotone versus far from monotone, this shows that adaptivity enables an exponential improvement in the query complexity of monotonicity testing for halfspaces.

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function f is a k-junta or epsilon-far from every k-junta must make ~Omega(k^{3/2}/ epsilon) many queries for a wide range of parameters k and epsilon. Our result dramatically improves previous lower bounds from [BGSMdW13,STW15], and is essentially optimal given Blais's non-adaptive junta tester from [Blais08], which makes ~O(k^{3/2})/epsilon queries. Combined with the adaptive tester of [Blais09] which makes O(k log k + k / epsilon) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.

We consider the fundamental derandomization problem of deterministically finding a satisfying assignment to a CNF formula that has many satisfying assignments. We give a deterministic algorithm which, given an n-variable poly(n)-clause CNF formula F that has at least ε2nsatisfying assignments, runs in time n(Õ(log log n)2) for ε ≥ 1/polylog(n) and outputs a satisfying assignment of F. Prior to our work the fastest known algorithm for this problem was simply to enumerate over all seeds of a pseudorandom generator for CNFs; using the best known PRGs for CNFs [DETT10], this takes time nΩ̃(log n)even for constant ε. Our approach is based on a new general framework relating deterministic search and deterministic approximate counting, which we believe may find further applications.

A weight-t halfspace is a Boolean function f(x) = sign(w1x1+ ⋯ + wnxn- θ) where each wiis an integer in {-t, . . . , t}. We give an explicit pseudorandom generator that δ-fools any intersection of k weight-t halfspaces with seed length poly(log n, log k, t, 1/δ). In particular, our result gives an explicit PRG that fools any intersection of any quasipoly(n) number of halfspaces of any polylog(n) weight to any 1/polylog(n) accuracy using seed length polylog(n). Prior to this work no explicit PRG with non-trivial seed length was known even for fooling intersections of n weight-1 halfspaces to constant accuracy. The analysis of our PRG fuses techniques from two different lines of work on unconditional pseudorandomness for different kinds of Boolean functions. We extend the approach of Harsha, Klivans and Meka [HKM12] for fooling intersections of regular halfspaces, and combine this approach with results of Bazzi [Baz07] and Razborov [Raz09] on bounded independence fooling CNF formulas. Our analysis introduces new couplingbased ingredients into the standard Lindeberg method for establishing quantitative central limit theorems and associated pseudorandomness results.

Despite decades of intensive research, efficient - or even sub-exponential time - distribution-free PAC learning algorithms are not known for many important Boolean function classes. In this work we suggest a new perspective on these learning problems, inspired by a surge of recent research in complexity theory, in which the goal is to determine whether and how much of a savings over a naive 2^n runtime can be achieved. We establish a range of exploratory results towards this end. In more detail, (1) We first observe that a simple approach building on known uniform-distribution learning results gives non-trivial distribution-free learning algorithms for several well-studied classes including AC0, arbitrary functions of a few linear threshold functions (LTFs), and AC0 augmented with mod_p gates. (2) Next we present an approach, based on the method of random restrictions from circuit complexity, which can be used to obtain several distribution-free learning algorithms that do not appear to be achievable by approach (1) above. The results achieved in this way include learning algorithms with non-trivial savings for LTF-of-AC0 circuits and improved savings for learning parity-of-AC0 circuits. (3) Finally, our third contribution is a generic technique for converting lower bounds proved using Neciporuk's method to learning algorithms with non-trivial savings. This technique, which is the most involved of our three approaches, yields distribution-free learning algorithms for a range of classes where previously even non-trivial uniform-distribution learning algorithms were not known; these classes include full-basis formulas, branching programs, span programs, etc. up to some fixed polynomial size.

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d ≥ 2, there is an explicit n -variable Boolean function f , computed by a linear-size depth- d formula, which is such that any depth-( d −1) circuit that agrees with f on (1/2 + o n (1)) fraction of all inputs must have size exp( n Ω (1/d) ). This answers an open question posed by Håstad in his Ph.D. thesis (Håstad 1986b). Our average-case depth hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, confirming a conjecture of Håstad (1986a), Cai (1986), and Babai (1987). We also use our result to show that there is no “approximate converse” to the results of Linial, Mansour, Nisan (Linial et al. 1993) and (Boppana 1997) on the total influence of bounded-depth circuits. A key ingredient in our proof is a notion of random projections which generalize random restrictions.

We show that any depth-d circuit for determining whether an n-node graph has an s-to-t path of length at most k must have size nΩ(k1/d/d) when k(n) ≤ n1/5, and nΩ(k1/5d/d) when k(n)≤ n. The previous best circuit size lower bounds were nkexp(−O(d)) (by Beame, Impagliazzo, and Pitassi (Computational Complexity 1998)) and nΩ((logk)/d) (following from a recent formula size lower bound of Rossman (STOC 2014)). Our lower bound is quite close to optimal, as a simple construction gives depth-d circuits of size nO(k2/d) for this problem (and strengthening our bound even to nkΩ(1/d) would require proving that undirected connectivity is not in NC1).

We show that any polynomial-size Frege refutation of a certain linear-size unsatisfiable 3-CNF formula over n variables must have depth Ω(√logn). This is an exponential improvement over the previous best results (Pitassi et al. 1993, Krajíček et al. 1995, Ben-Sasson 2002) which give Ω(loglogn) lower bounds.

Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean functions in terms of the minimum number of negations in any circuit computing them, a complexity measure that interpolates between monotone functions and the class of all functions. We study this generalization of monotonicity from the vantage point of learning theory, establishing nearly matching upper and lower bounds on the uniform-distribution learnability of circuits in terms of the number of negations they contain. Our upper bounds are based on a new structural characterization of negation-limited circuits that extends a classical result of A.A. Markov. Our lower bounds, which employ Fourier-analytic tools from hardness amplification, give new results even for circuits with no negations (i.e. monotone functions).

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d ≥ 2, there is an explicit n-variable Boolean function f, computed by a linear-size depth-d formula, which is such that any depth-(d - 1) circuit that agrees with f on (1/2 + on(1)) fraction of all inputs must have size exp(nΩ(1/d)). This answers an open question posed by Hastad in his Ph.D. thesis [Has86b]. Our average-case depth hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, confirming a conjecture of Hastad [Has86a], Cai [Cai86], and Babai [Bab87]. We also use our result to show that there is no “approximate converse” to the results of Linial, Mansour, Nisan [LMN93] and Boppana [Bop97] on the total influence of constant-depth circuits, thus answering a question posed by Kalai [Kal12] and Hatami [Hat14]. A key ingredient in our proof is a notion of random projections which generalize random restrictions.

A function f is d-resilient if all its Fourier coefficients of degree at most d are zero, i.e. f is uncorrelated with all low-degree parities. We study the notion of approximate resilience of Boolean functions, where we say that f is α-approximately d-resilient if f is α-close to a [-1, 1]-valued d-resilient function in ℓ1 distance. We show that approximate resilience essentially characterizes the complexity of agnostic learning of a concept class C over the uniform distribution. Roughly speaking, if all functions in a class C are far from being d-resilient then C can be learned agnostically in time nO(d) and conversely, if C contains a function close to being d-resilient then agnostic learning of C in the statistical query (SQ) framework of Kearns has complexity of at least nΩ(d). Focusing on monotone Boolean functions, we exhibit the existence of near-optimal α-approximately -resilient monotone functions for all α > 0. Prior to our work, it was conceivable even that every monotone function is Ω(1)-far from any 1-resilient function. Furthermore, we construct simple, explicit monotone functions based on Tribes and CycleRun that are close to highly resilient functions. Our constructions are based on general resilience analysis and amplification techniques we introduce. These structural results, together with the characterization, imply nearly optimal lower bounds for agnostic learning of monotone juntas, a natural variant of the well-studied junta learning problem. In particular we show that no SQ algorithm can efficiently agnostically learn monotone k-juntas for any k = ω(1) and any constant error less than 1/2.

We prove a lower bound of Ω(n1/2-c), for all c> 0, on the query complexity of (two-sided error) non-adaptive algorithms for testing whether an n-variable Boolean function is monotone versus constant-far from monotone. This improves a ~Ω(n1/5) lower bound for the same problem that was obtained in [6], and is very close to the recent upper bound of ~O(n1/2/ε2) by Khot et al. [13].

We study the complexity of approximating Boolean functions with disjunctive normal forms (DNFs) and other depth-2 circuits, exploring two main directions: universal bounds on the approximability of all Boolean functions, and the approximability of the parity function. In the first direction, our main positive results are the first nontrivial universal upper bounds on approximability by DNFs: (a) every Boolean function can be $\epsilon$-approximated by a DNF of size $O_\epsilon(2^n/\log n)$, and (b) every Boolean function can be $\epsilon$-approximated by a DNF of width $c_\epsilon\, n$, where $c_\epsilon < 1$. Our techniques extend broadly to give strong universal upper bounds on approximability by various depth-2 circuits that generalize DNFs, including the intersection of halfspaces, low-degree Polynomial threshold functions, and unate functions. We show that the parameters of our constructions almost match the information-theoretic inapproximability of a random function. In the second direction our main positive result is the construction of an explicit DNF that approximates the following parity function: ${\sf PAR}_n$ can be $\epsilon$-approximated by a DNF of size $2^{(1-2\epsilon)n}$ and width $(1-2\epsilon)n$. Using Fourier analytic tools we show that our construction is essentially optimal not just within the class of DNFs but also within the far more expressive classes of the intersection of halfspaces and intersection of unate functions.

In this work, we study the parity complexity measures pCmin[f] and PDT[f]. Pcmin[f] is the parity kill number of f, the fewest number of parities on the input variables one has to fix in order to "kill" f, i.e. To make it constant. PDT[f] is the depth of the shortest emph{parity decision tree} which computes f. These complexity measures have in recent years become increasingly important in the fields of communication complexity [1], [2], [3], [4] and pseudorandomness [5], [6], [7]. Our main result is a composition theorem for pCmin. The k-th power of f, denoted f^{circ k}, is the function which results from composing f with itself k times. We prove that if f is not a parity function, then pCmin[f^{circ k}] geq Omega(Cmin[f]^{k}). In other words, the parity kill number of f is essentially super multiplicative in the normal kill number of f (also known as the minimum certificate complexity). As an application of our composition theorem, we show lower bounds on the parity complexity measures of sort^{circ k} and HI^{circ k}. Here sort is the sort function due to Ambainis [8], and HI is Kushilevitz's hemi-icosahedron function [9]. In doing so, we disprove a conjecture of Montanaro and Osborne [2] which had applications to communication complexity and computational learning theory. In addition, we give new lower bounds for conjectures of [2], [3] and [4].

We consider the problem of testing whether an unknown Boolean function f : {- 1, 1}n→ {-1, 1} is monotone versus ε-far from every monotone function. The two main results of this paper are a new lower bound and a new algorithm for this well-studied problem. Lower bound: We prove an Ω̅(n1/5) lower bound on the query complexity of any non-adaptive two-sided error algorithm for testing whether an unknown Boolean function f is monotone versus constant-far from monotone. This gives an exponential improvement on the previous lower bound of Ω(log n) due to Fischer et al. [1]. We show that the same lower bound holds for monotonicity testing of Boolean-valued functions over hypergrid domains {1,···, m}nfor all m ≥ 2. Upper bound: We present an O(n5/6) poly(1/ε)-query algorithm that tests whether an unknown Boolean function f is monotone versus ε-far from monotone. Our algorithm, which is non-adaptive and makes one-sided error, is a modified version of the algorithm of Chakrabarty and Seshadhri[2], which makes O(n7/8) poly(1/ε) queries.

Our main result is a formulation and proof of the reverse hypercontractive inequality in the sum-of-squares (SOS) proof system. As a consequence we show that for any constant 0 < γ ≤ 1/4, the SOS/Lasserre SDP hierarchy at degree certifies the statement “the maximum independent set in the Frankl–Rödl graph has fractional size o(1)”. Here is the graph with V = {0,1}n and (x,y) ∊ E whenever Δ(x, y) = (1 – γ)n (an even integer). In particular, we show the degree-4 SOS algorithm certifies the chromatic number lower bound “ ”, even though is the canonical integrality gap instance for which standard SDP relaxations cannot even certify “ ”. Finally, we also give an SOS proof of (a generalization of) the sharp (2, q)-hypercontractive inequality for any even integer q.

We give the first nontrivial upper bounds on the Boolean average sensitivity and noise sensitivity of degree-$d$ polynomial threshold functions (PTFs). Our bound on the Boolean average sensitivity of PTFs represents the first progress toward the resolution of a conjecture of Gotsman and Linial [Combinatorica, 14 (1994), pp. 35--50], which states that the symmetric function slicing the middle $d$ layers of the Boolean hypercube has the highest average sensitivity of all degree-$d$ PTFs. Via the $L_1$ polynomial regression algorithm of Kalai et al. [SIAM J. Comput., 37 (2008), pp. 1777--1805], our bound on Boolean noise sensitivity yields the first polynomial-time agnostic learning algorithm for the broad class of constant-degree PTFs under the uniform distribution. To obtain our bound on the Boolean average sensitivity of PTFs, we generalize the “critical-index” machinery of [R. Servedio, Comput. Complexity, 16 (2007), pp. 180--209] (which in that work applies to halfspaces, i.e., degree-1 PTFs) to general PTFs. Together with the “invariance principle” of [E. Mossel, R. O'Donnell, and K. Oleszkiewicz, Ann. of Math. (2), 171 (2010), pp. 295--341], this allows us to essentially reduce the Boolean setting to the Gaussian setting. The main ingredients used to obtain our bound in the Gaussian setting are tail bounds and anticoncentration bounds on low-degree polynomials in Gaussian random variables [S. Janson, Gaussian Hilbert Spaces, Cambridge University Press, Cambridge, UK, 1997; A. Carbery and J. Wright, Math. Res. Lett., 8 (2001), pp. 233--248]. Our bound on Boolean noise sensitivity is achieved via a simple reduction from upper bounds on average sensitivity of Boolean PTFs to corresponding bounds on noise sensitivity.

We study the complexity of approximating Boolean functions with DNFs and other depth-2 circuits, exploring two main directions: universal bounds on the approximability of all Boolean functions, and the approximability of the parity function. In the first direction, our main positive results are the first non-trivial universal upper bounds on appropriability by DNFs: : Every Boolean function can be ε-approximated by a DNF of size Oε(2n/ log n). : Every Boolean function can be ε-approximated by a DNF of width cεn, where cεncan be ε-approximated by a DNF of size 2(1-2ε)nand width (1 - 2ε)n. Using Fourier analytic tools we show that our construction is essentially optimal not just within the class of DNFs, but also within the far more expressive classes of the intersection of halfspaces and intersection of unate functions.

Let bS = bX_1 + ·s + bX_n be a sum of n independent integer random variables bX_i, where each bX_i is supported on 0, 1, ·, k-1 but otherwise may have an arbitrary distribution (in particular the bX_i's need not be identically distributed). How many samples are required to learn the distribution bS to high accuracy? In this paper we show that the answer is completely independent of n, and moreover we give a computationally efficient algorithm which achieves this low sample complexity. More precisely, our algorithm learns any such bS to ε-accuracy (with respect to the total variation distance between distributions) using poly(k, 1/ε) samples, independent of n. Its running time is poly(k, 1/ε) in the standard word RAM model. Thus we give a broad generalization of the main result of DDS12stoc which gave a similar learning result for the special case k=2 (when the distribution bS is a Poisson Binomial Distribution). Prior to this work, no nontrivial results were known for learning these distributions even in the case k=3. A key difficulty is that, in contrast to the case of k = 2, sums of independent 0, 1, 2-valued random variables may behave very differently from (discretized) normal distributions, and in fact may be rather complicated - they are not log-concave, they can be θ(n)-modal, there is no relationship between Kolmogorov distance and total variation distance for the class, etc. Nevertheless, the heart of our learning result is a new limit theorem which characterizes what the sum of an arbitrary number of arbitrary independent 0, 1, ·, k-1-valued random variables may look like. Previous limit theorems in this setting made strong assumptions on the "shift invariance" of the random variables bX_i in order to force a discretized normal limit. We believe that our new limit theorem, as the first result for truly arbitrary sums of independent 0, 1, ·, k-1-valued random variables, is of independent interest.

We give a "regularity lemma" for degree-d polynomial threshold functions (PTFs) over the Boolean cube {-1,1}n. Roughly speaking, this result shows that every degree-d PTF can be decomposed into a constant number of subfunctions such that almost all of the subfunctions are close to being regular PTFs. Here a "regular" PTF is a PTF sign(p(x)) where the influence of each variable on the polynomial p(x) is a small fraction of the total influence of p. As an application of this regularity lemma, we prove that for any constants d ≥ 1, ϵ > 0, every degree-d PTF over n variables can be approximated to accuracy eps by a constant degree PTF that has integer weights of total magnitude O(nd). This weight bound is shown to be optimal up to logarithmic factors.

We give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of degree-d polynomial threshold functions (PTFs). These bounds hold both for PTFs over the Boolean hypercube {-1,1}n and for PTFs over Rn under the standard n-dimensional Gaussian distribution N(0,In). Our bound on the Boolean average sensitivity of PTFs represents progress towards the resolution of a conjecture of Gotsman and Linial [17], which states that the symmetric function slicing the middle d layers of the Boolean hypercube has the highest average sensitivity of all degree-d PTFs. Via the L1 polynomial regression algorithm of Kalai et al. [22], our bounds on Gaussian and Boolean noise sensitivity yield polynomial-time agnostic learning algorithms for the broad class of constant-degree PTFs under these input distributions.