Li-Yang Tan

FOCS Conference 2025 Conference Paper

Computational-Statistical Tradeoffs from NP-hardness

• Guy Blanc
• Caleb Koch 0001
• Carmen Strassle
• Li-Yang Tan

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).

FOCS Conference 2024 Conference Paper

Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems

• Caleb Koch 0001
• Carmen Strassle
• Li-Yang Tan

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$ /log n ) (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.

FOCS Conference 2024 Conference Paper

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem

• Guy Blanc
• Alexandre Hayderi
• Caleb Koch 0001
• Li-Yang Tan

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.

FOCS Conference 2023 Conference Paper

A strong composition theorem for junta complexity and the boosting of property testers

• Guy Blanc
• Caleb Koch 0001
• Carmen Strassle
• Li-Yang Tan

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.

NeurIPS Conference 2023 Conference Paper

Harnessing the power of choices in decision tree learning

• Guy Blanc
• Jane Lange
• Chirag Pabbaraju
• Colin Sullivan
• Li-Yang Tan
• Mo Tiwari

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.

STOC Conference 2023 Conference Paper

Lifting Uniform Learners via Distributional Decomposition

• Guy Blanc
• Jane Lange
• Ali Malik
• Li-Yang Tan

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. A key technical ingredient is an algorithm which, given the aforementioned access to D , produces an optimal decision tree decomposition of D : an approximation of D as a mixture of uniform distributions over disjoint subcubes. With this decomposition in hand, we run the uniform-distribution learner on each subcube and combine the hypotheses using the decision tree. This algorithmic decomposition lemma also yields new algorithms for learning decision tree distributions with runtimes that exponentially improve on the prior state of the art—results of independent interest in distribution learning.

FOCS Conference 2023 Conference Paper

Properly learning decision trees with queries is NP-hard

• Caleb Koch 0001
• Carmen Strassle
• Li-Yang Tan

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.

SODA Conference 2023 Conference Paper

Single-Pass Streaming Algorithms for Correlation Clustering

• Soheil Behnezhad
• Moses Charikar
• Weiyun Ma
• Li-Yang Tan

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 > 10 5 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.

SODA Conference 2023 Conference Paper

Superpolynomial lower bounds for decision tree learning and testing

• Caleb Koch 0001
• Carmen Strassle
• Li-Yang Tan

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 ○ construct a small decision tree approximator for f under D, and ○ decide if there is a small decision tree approximator for f under D. Our results imply new lower bounds for distribution-free PAC learning and testing of decision trees, settings in which the algorithm only has restricted access to f and D. Specifically, we get that: ○ n -variable size- s decision trees cannot be properly PAC learned in time n Õ(log log s), and ○ depth- d decision trees cannot be tested in time exp( d O(1) ). For learning, the previous best lower bound only ruled out poly( n )-time algorithms (Alekhnovich, Braverman, Feldman, Klivans, and Pitassi, 2009). For testing, recent work gives similar though incomparable lower bounds in the setting where f is random and D is nonexplicit (Blais, Ferreira Pinto Jr. , and Harms, 2021). Assuming a plausible conjecture on the hardness of SET-COVER, we show that our lower bound for properly PAC learning decision trees can be improved to n Ω(log s ), matching the best known upper bound of n O(log s ) due to Ehrenfeucht and Haussler (1989). We obtain our results within a unified framework that leverages recent progress in two different lines of work: the inapproximability of SET-COVER and XOR lemmas for query complexity. Our framework is versatile and yields results for related concept classes such as juntas and DNF formulas. ∗ The full version of the paper can be accessed at https: //arxiv. org/abs/2210. 06375

SAT Conference 2022 Conference Paper

A Generalization of the Satisfiability Coding Lemma and Its Applications

• Milan Mossé
• Harry Sha
• Li-Yang Tan

The seminal Satisfiability Coding Lemma of Paturi, Pudlák, and Zane is a coding scheme for satisfying assignments of k-CNF formulas. We generalize it to give a coding scheme for implicants and use this generalized scheme to establish new structural and algorithmic properties of prime implicants of k-CNF formulas. Our first application is a near-optimal bound of n⋅ 3^{n(1-Ω(1/k))} on the number of prime implicants of any n-variable k-CNF formula. This resolves an open problem from the Ph. D. thesis of Talebanfard, who proved such a bound for the special case of constant-read k-CNF formulas. Our proof is algorithmic in nature, yielding an algorithm for computing the set of all prime implicants - the Blake Canonical Form - of a given k-CNF formula. The problem of computing the Blake Canonical Form of a given function is a classic one, dating back to Quine, and our work gives the first non-trivial algorithm for k-CNF formulas.

ICML Conference 2022 Conference Paper

A query-optimal algorithm for finding counterfactuals

• Guy Blanc
• Caleb Koch 0001
• Jane Lange
• Li-Yang Tan

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.

FOCS Conference 2022 Conference Paper

Almost 3-Approximate Correlation Clustering in Constant Rounds

• Soheil Behnezhad
• Moses Charikar
• Weiyun Ma
• Li-Yang Tan

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].

ICML Conference 2022 Conference Paper

Popular decision tree algorithms are provably noise tolerant

• Guy Blanc
• Jane Lange
• Ali Malik
• Li-Yang Tan

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.

STOC Conference 2022 Conference Paper

The query complexity of certification

• Guy Blanc
• Caleb Koch 0001
• Jane Lange
• Li-Yang Tan

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 ⋆ . For monotone functions, a classic local search algorithm of Angluin accomplishes this task with n queries, which we show is optimal for local search algorithms. Our main result is a new algorithm for certifying monotone functions with O ( k 8 log n ) queries, which comes close to matching the information-theoretic lower bound of Ω( k log n ). The design and analysis of our algorithm are based on a new connection to threshold phenomena in monotone functions. We further prove exponential-in- k lower bounds when f is non-monotone, and when f is monotone but the algorithm is only given random examples of f . These lower bounds show that assumptions on the structure of f and query access to it are both necessary for the polynomial dependence on k that we achieve.

FOCS Conference 2021 Conference Paper

Properly learning decision trees in almost polynomial time

• Guy Blanc
• Jane Lange
• Mingda Qiao
• Li-Yang Tan

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.

NeurIPS Conference 2021 Conference Paper

Provably efficient, succinct, and precise explanations

• Guy Blanc
• Jane Lange
• Li-Yang Tan

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.

SODA Conference 2021 Conference Paper

Query strategies for priced information, revisited

• Guy Blanc
• Jane Lange
• Li-Yang Tan

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.

FOCS Conference 2021 Conference Paper

Sharper bounds on the Fourier concentration of DNFs

• Victor Lecomte
• Li-Yang Tan

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.

FOCS Conference 2021 Conference Paper

Tradeoffs for small-depth Frege proofs

• Toniann Pitassi
• Prasanna Ramakrishnan
• Li-Yang Tan

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.

NeurIPS Conference 2020 Conference Paper

Estimating decision tree learnability with polylogarithmic sample complexity

• Guy Blanc
• Neha Gupta
• Jane Lange
• Li-Yang Tan

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$.

STOC Conference 2020 Conference Paper

Fooling Gaussian PTFs via local hyperconcentration

• Ryan O'Donnell
• Rocco A. Servedio
• Li-Yang Tan

We give a pseudorandom generator that fools degree- d polynomial threshold functions over n -dimensional Gaussian space with seed length d O (log d ) · log n . All previous generators had a seed length with at least a 2 d dependence on d . The key new ingredient is our Local Hyperconcentration Theorem , which shows that every degree- d Gaussian polynomial is hyperconcentrated almost everywhere at scale d − O (log d ) .

ICML Conference 2020 Conference Paper

Provable guarantees for decision tree induction: the agnostic setting

• Guy Blanc
• Jane Lange
• Li-Yang Tan

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.

NeurIPS Conference 2020 Conference Paper

Universal guarantees for decision tree induction via a higher-order splitting criterion

• Guy Blanc
• Neha Gupta
• Jane Lange
• Li-Yang Tan

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$.

STOC Conference 2019 Conference Paper

Fooling polytopes

• Ryan O'Donnell
• Rocco A. Servedio
• Li-Yang Tan

SODA Conference 2019 Conference Paper

Pseudorandomness for read-k DNF formulas

• Rocco A. Servedio
• Li-Yang Tan

FOCS Conference 2018 Conference Paper

Non-Malleable Codes for Small-Depth Circuits

• Marshall Ball
• Dana Dachman-Soled
• Siyao Guo 0001
• Tal Malkin
• Li-Yang Tan

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. AC 0 tampering functions), our codes have codeword length n = k 1+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 2 O(√k). Our construction remains efficient for circuit depths as large as Θ(log(n)/loglog(n)) (indeed, our codeword length remains n ≤ k 1+ε ), and extending our result beyond this would require separating P from NC 1. 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.

FOCS Conference 2017 Conference Paper

Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time

• Rocco A. Servedio
• Li-Yang Tan

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 ε2 n satisfying 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.

FOCS Conference 2017 Conference Paper

Fooling Intersections of Low-Weight Halfspaces

• Rocco A. Servedio
• Li-Yang Tan

A weight-t halfspace is a Boolean function f(x) = sign(w 1 x 1 + ⋯ + w n x n - θ) where each w i is 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.

STOC Conference 2016 Conference Paper

Near-optimal small-depth lower bounds for small distance connectivity

• Xi Chen 0001
• Igor C. Oliveira 0001
• Rocco A. Servedio
• Li-Yang Tan

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 Ω( k 1/ d / d ) when k ( n ) ≤ n 1/5 , and n Ω( k 1/5 d / d ) when k ( n )≤ n . The previous best circuit size lower bounds were n k exp(− O ( d )) (by Beame, Impagliazzo, and Pitassi (Computational Complexity 1998)) and n Ω((log k )/ 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 n O ( k 2/ d ) for this problem (and strengthening our bound even to n k Ω(1/ d ) would require proving that undirected connectivity is not in NC 1 ). Our proof is by reduction to a new lower bound on the size of small-depth circuits computing a skewed variant of the “Sipser functions” that have played an important role in classical circuit lower bounds. A key ingredient in our proof of the required lower bound for these Sipser-like functions is the use of random projections , an extension of random restrictions which were recently employed by Rossman, Servedio, and Tan (FOCS 2015). Random projections allow us to obtain sharper quantitative bounds while employing simpler arguments, both conceptually and technically, than in the previous works.

STOC Conference 2016 Conference Paper

Poly-logarithmic Frege depth lower bounds via an expander switching lemma

• Toniann Pitassi
• Benjamin Rossman
• Rocco A. Servedio
• Li-Yang Tan

We show that any polynomial-size Frege refutation of a certain linear-size unsatisfiable 3-CNF formula over n variables must have depth Ω(√log n ). This is an exponential improvement over the previous best results (Pitassi et al. 1993, Krajíček et al. 1995, Ben-Sasson 2002) which give Ω(loglog n ) lower bounds. The 3-CNF formulas which we use to establish this result are Tseitin contradictions on 3-regular expander graphs. In more detail, our main result is a proof that for every d , any depth- d Frege refutation of the Tseitin contradiction over these n -node graphs must have size n Ω((log n )/ d 2 ) . A key ingredient of our approach is a new switching lemma for a carefully designed random restriction process over these expanders. These random restrictions reduce a Tseitin instance on a 3-regular n -node expander to a Tseitin instance on a random subgraph which is a topological embedding of a 3-regular n ′-node expander, for some n ′ which is not too much less than n . Our result involves Ω(√log n ) iterative applications of this type of random restriction.

FOCS Conference 2015 Conference Paper

An Average-Case Depth Hierarchy Theorem for Boolean Circuits

• Benjamin Rossman
• Rocco A. Servedio
• Li-Yang Tan

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 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.

SODA Conference 2015 Conference Paper

Approximate resilience, monotonicity, and the complexity of agnostic learning

• Dana Dachman-Soled
• Vitaly Feldman
• Li-Yang Tan
• Andrew Wan
• Karl Wimmer

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 n O ( 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.

STOC Conference 2015 Conference Paper

Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries

• Xi Chen 0001
• Anindya De
• Rocco A. Servedio
• Li-Yang Tan

We prove a lower bound of Ω(n 1/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 ~Ω(n 1/5 ) lower bound for the same problem that was obtained in [6], and is very close to the recent upper bound of ~O(n 1/2 /ε 2 ) by Khot et al. [13].

SODA Conference 2014 Conference Paper

Hypercontractive inequalities via SOS, and the Frankl-Rödl graph

• Manuel Kauers
• Ryan O'Donnell
• Li-Yang Tan
• Yuan Zhou 0007

FOCS Conference 2014 Conference Paper

New Algorithms and Lower Bounds for Monotonicity Testing

• Xi Chen 0001
• Rocco A. Servedio
• Li-Yang Tan

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 Ω̅(n 1/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} n for all m ≥ 2. Upper bound: We present an O(n 5/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(n 7/8 ) poly(1/ε) queries.

FOCS Conference 2013 Conference Paper

Learning Sums of Independent Integer Random Variables

• Constantinos Daskalakis
• Ilias Diakonikolas
• Ryan O'Donnell
• Rocco A. Servedio
• Li-Yang Tan

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.

STOC Conference 2010 Conference Paper

Bounding the average sensitivity and noise sensitivity of polynomial threshold functions

• Ilias Diakonikolas
• Prahladh Harsha
• Adam R. Klivans
• Raghu Meka
• Prasad Raghavendra
• Rocco A. Servedio
• Li-Yang Tan

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 R n under the standard n-dimensional Gaussian distribution N(0,I n ). 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 L 1 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.