The Algebra of Equality Proofs. - Aaron Stump; Li-Yang Tan (RTA, 2005)

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 (STOC, 2010)

On the Distribution of the Fourier Spectrum of Halfspaces - Ilias Diakonikolas; Ragesh Jaiswal; Rocco A. Servedio; Li-Yang Tan; Andrew Wan (CoRR, 2012)

Analysis of Boolean Functions - Li-Yang Tan (CoRR, 2012)

Hypercontractive inequalities via SOS, with an application to Vertex-Cover - Manuel Kauers; Ryan O'Donnell; Li-Yang Tan; Yuan Zhou 007 (CoRR, 2012)

Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions. - Rocco A. Servedio; Li-Yang Tan; Justin Thaler (Electron. Colloquium Comput. Complex., 2012)

On the Average Sensitivity and Density of k-CNF Formulas. - Dominik Scheder; Li-Yang Tan (APPROX-RANDOM, 2013)

Learning Sums of Independent Integer Random Variables. - Constantinos Daskalakis; Ilias Diakonikolas; Ryan O'Donnell; Rocco A. Servedio; Li-Yang Tan (FOCS, 2013)

A Composition Theorem for the Fourier Entropy-Influence Conjecture. - Ryan O'Donnell; Li-Yang Tan (ICALP (1), 2013)

Hypercontractivity Via the Entropy Method. - Eric Blais; Li-Yang Tan (Theory Comput., 2013)

A Composition Theorem for Parity Kill Number. - Ryan O'Donnell; John Wright 004; Yu Zhao 032; Xiaorui Sun; Li-Yang Tan (CCC, 2014)

New Algorithms and Lower Bounds for Monotonicity Testing. - Xi Chen 001; Rocco A. Servedio; Li-Yang Tan (FOCS, 2014)

On DNF Approximators for Monotone Boolean Functions. - Eric Blais; Johan Håstad; Rocco A. Servedio; Li-Yang Tan (ICALP (1), 2014)

Hypercontractive inequalities via SOS, and the Frankl-Rödl graph. - Manuel Kauers; Ryan O'Donnell; Li-Yang Tan; Yuan Zhou 007 (SODA, 2014)

Learning circuits with few negations. - Eric Blais; Clément L. Canonne; Igor Carboni Oliveira; Rocco A. Servedio; Li-Yang Tan (Electron. Colloquium Comput. Complex., 2014)

Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions. - Ilias Diakonikolas; Prasad Raghavendra; Rocco A. Servedio; Li-Yang Tan (SIAM J. Comput., 2014)

A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions. - Ilias Diakonikolas; Rocco A. Servedio; Li-Yang Tan; Andrew Wan (Theory Comput., 2014)

New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover. - Per Austrin; Ryan O'Donnell; Li-Yang Tan; John Wright 004 (ACM Trans. Comput. Theory, 2014)

Analytic Methods in Concrete Complexity. - Li-Yang Tan (2014)

Adaptivity Helps for Testing Juntas. - Rocco A. Servedio; Li-Yang Tan; John Wright 004 (CCC, 2015)

Algorithmic Signaling of Features in Auction Design. - Shaddin Dughmi; Nicole Immorlica; Ryan O'Donnell; Li-Yang Tan (SAGT, 2015)

Approximate resilience, monotonicity, and the complexity of agnostic learning. - Dana Dachman-Soled; Vitaly Feldman; Li-Yang Tan; Andrew Wan; Karl Wimmer (SODA, 2015)

Boolean Function Monotonicity Testing Requires (Almost) n1/2 Non-adaptive Queries. - Xi Chen 001; Anindya De; Rocco A. Servedio; Li-Yang Tan (STOC, 2015)

Noise Stable Halfspaces are Close to Very Small Juntas. - Ilias Diakonikolas; Ragesh Jaiswal; Rocco A. Servedio; Li-Yang Tan; Andrew Wan (Chic. J. Theor. Comput. Sci., 2015)

An inequality for the Fourier spectrum of parity decision trees. - Eric Blais; Li-Yang Tan; Andrew Wan (CoRR, 2015)

An average-case depth hierarchy theorem for Boolean circuits. - Benjamin Rossman; Rocco A. Servedio; Li-Yang Tan (Electron. Colloquium Comput. Complex., 2015)

Approximating Boolean Functions with Depth-2 Circuits. - Eric Blais; Li-Yang Tan (SIAM J. Comput., 2015)

Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles, and Boolean Circuits. - Benjamin Rossman; Rocco A. Servedio; Li-Yang Tan (SIGACT News, 2015)

Near-optimal small-depth lower bounds for small distance connectivity. - Xi Chen 001; Igor C. Oliveira 001; Rocco A. Servedio; Li-Yang Tan (STOC, 2016)

Poly-logarithmic Frege depth lower bounds via an expander switching lemma. - Toniann Pitassi; Benjamin Rossman; Rocco A. Servedio; Li-Yang Tan (STOC, 2016)

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. - Xi Chen 001; Rocco A. Servedio; Li-Yang Tan; Erik Waingarten (APPROX-RANDOM, 2017)

Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time. - Rocco A. Servedio; Li-Yang Tan (FOCS, 2017)

Fooling Intersections of Low-Weight Halfspaces. - Rocco A. Servedio; Li-Yang Tan (FOCS, 2017)

What Circuit Classes Can Be Learned with Non-Trivial Savings?. - Rocco A. Servedio; Li-Yang Tan (ITCS, 2017)

Settling the query complexity of non-adaptive junta testing. - Xi Chen 001; Rocco A. Servedio; Li-Yang Tan; Erik Waingarten; Jinyu Xie (Electron. Colloquium Comput. Complex., 2017)

An Average-Case Depth Hierarchy Theorem for Boolean Circuits. - Johan Håstad; Benjamin Rossman; Rocco A. Servedio; Li-Yang Tan (J. ACM, 2017)

Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits. - Rocco A. Servedio; Li-Yang Tan (APPROX-RANDOM, 2018)

Non-Malleable Codes for Small-Depth Circuits. - Marshall Ball; Dana Dachman-Soled; Siyao Guo; Tal Malkin; Li-Yang Tan (Electron. Colloquium Comput. Complex., 2018)

Fooling Polytopes. - Ryan O'Donnell; Rocco A. Servedio; Li-Yang Tan (Electron. Colloquium Comput. Complex., 2018)

Pseudorandomness for read-k DNF formulas. - Rocco A. Servedio; Li-Yang Tan (SODA, 2019)

Constructive derandomization of query algorithms. - Guy Blanc; Jane Lange; Li-Yang Tan (CoRR, 2019)

Top-down induction of decision trees: rigorous guarantees and inherent limitations. - Guy Blanc; Jane Lange; Li-Yang Tan (Electron. Colloquium Comput. Complex., 2019)

Provable guarantees for decision tree induction: the agnostic setting. - Guy Blanc; Jane Lange; Li-Yang Tan (ICML, 2020)

Estimating decision tree learnability with polylogarithmic sample complexity. - Guy Blanc; Neha Gupta 002; Jane Lange; Li-Yang Tan (NeurIPS, 2020)

Universal guarantees for decision tree induction via a higher-order splitting criterion. - Guy Blanc; Neha Gupta 002; Jane Lange; Li-Yang Tan (NeurIPS, 2020)

Unconditional Lower Bounds for Adaptive Massively Parallel Computation. - Moses Charikar; Weiyun Ma; Li-Yang Tan (SPAA, 2020)

Fooling Gaussian PTFs via local hyperconcentration. - Ryan O'Donnell; Rocco A. Servedio; Li-Yang Tan (STOC, 2020)

New lower bounds for Massively Parallel Computation from query complexity. - Moses Charikar; Weiyun Ma; Li-Yang Tan (CoRR, 2020)

Testing and reconstruction via decision trees. - Guy Blanc; Jane Lange; Li-Yang Tan (CoRR, 2020)

Non-Malleability against Polynomial Tampering. - Marshall Ball; Eshan Chattopadhyay; Jyun-Jie Liao; Tal Malkin; Li-Yang Tan (Electron. Colloquium Comput. Complex., 2020)

The Power of Many Samples in Query Complexity. - Andrew Bassilakis; Andrew Drucker; Mika Göös; Lunjia Hu; Weiyun Ma; Li-Yang Tan (Electron. Colloquium Comput. Complex., 2020)

Decision Tree Heuristics Can Fail, Even in the Smoothed Setting. - Guy Blanc; Jane Lange; Mingda Qiao; Li-Yang Tan (APPROX-RANDOM, 2021)

Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma. - Rocco A. Servedio; Li-Yang Tan (APPROX-RANDOM, 2021)

Sharper bounds on the Fourier concentration of DNFs. - Victor Lecomte; Li-Yang Tan (FOCS, 2021)

Tradeoffs for small-depth Frege proofs. - Toniann Pitassi; Prasanna Ramakrishnan; Li-Yang Tan (FOCS, 2021)

Learning Stochastic Decision Trees. - Guy Blanc; Jane Lange; Li-Yang Tan (ICALP, 2021)

Provably efficient, succinct, and precise explanations. - Guy Blanc; Jane Lange; Li-Yang Tan (NeurIPS, 2021)

Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity. - Moses Charikar; Weiyun Ma; Li-Yang Tan (PODC, 2021)

Query strategies for priced information, revisited. - Guy Blanc; Jane Lange; Li-Yang Tan (SODA, 2021)

Fooling Gaussian PTFs via Local Hyperconcentration. - Ryan O'Donnell; Rocco A. Servedio; Li-Yang Tan; Daniel Kane 001 (CoRR, 2021)

On the Power and Limitations of Branch and Cut. - Noah Fleming; Mika Göös; Russell Impagliazzo; Toniann Pitassi; Robert Robere; Li-Yang Tan; Avi Wigderson (Electron. Colloquium Comput. Complex., 2021)

The Composition Complexity of Majority. - Victor Lecomte; Prasanna Ramakrishnan; Li-Yang Tan (CCC, 2022)

On the power of adaptivity in statistical adversaries. - Guy Blanc; Jane Lange; Ali Malik; Li-Yang Tan (COLT, 2022)

Almost 3-Approximate Correlation Clustering in Constant Rounds. - Soheil Behnezhad; Moses Charikar; Weiyun Ma; Li-Yang Tan (FOCS, 2022)

Reconstructing Decision Trees. - Guy Blanc; Jane Lange; Li-Yang Tan (ICALP, 2022)

A query-optimal algorithm for finding counterfactuals. - Guy Blanc; Caleb Koch 001; Jane Lange; Li-Yang Tan (ICML, 2022)

Popular decision tree algorithms are provably noise tolerant. - Guy Blanc; Jane Lange; Ali Malik; Li-Yang Tan (ICML, 2022)

A Generalization of the Satisfiability Coding Lemma and Its Applications. - Milan Mossé; Harry Sha; Li-Yang Tan (SAT, 2022)

The query complexity of certification. - Guy Blanc; Caleb Koch 001; Jane Lange; Li-Yang Tan (STOC, 2022)

Open Problem: Properly learning decision trees in polynomial time? - Guy Blanc; Jane Lange; Mingda Qiao; Li-Yang Tan (CoRR, 2022)

Properly Learning Decision Trees in almost Polynomial Time. - Guy Blanc; Jane Lange; Mingda Qiao; Li-Yang Tan (J. ACM, 2022)

Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas. - Rocco A. Servedio; Li-Yang Tan (Adv. Math. Commun., 2022)

Multitask Learning via Shared Features: Algorithms and Hardness. - Konstantina Bairaktari; Guy Blanc; Li-Yang Tan; Jonathan R. Ullman; Lydia Zakynthinou (COLT, 2023)

A strong composition theorem for junta complexity and the boosting of property testers. - Guy Blanc; Caleb Koch 001; Carmen Strassle; Li-Yang Tan (FOCS, 2023)

Properly learning decision trees with queries is NP-hard. - Caleb Koch 001; Carmen Strassle; Li-Yang Tan (FOCS, 2023)

Certification with an NP Oracle. - Guy Blanc; Caleb Koch 001; Jane Lange; Carmen Strassle; Li-Yang Tan (ITCS, 2023)

Harnessing the power of choices in decision tree learning. - Guy Blanc; Jane Lange; Chirag Pabbaraju; Colin Sullivan; Li-Yang Tan; Mo Tiwari (NeurIPS, 2023)

Single-Pass Streaming Algorithms for Correlation Clustering. - Soheil Behnezhad; Moses Charikar; Weiyun Ma; Li-Yang Tan (SODA, 2023)

Superpolynomial lower bounds for decision tree learning and testing. - Caleb Koch 001; Carmen Strassle; Li-Yang Tan (SODA, 2023)

Lifting Uniform Learners via Distributional Decomposition. - Guy Blanc; Jane Lange; Ali Malik; Li-Yang Tan (STOC, 2023)

A Strong Direct Sum Theorem for Distributional Query Complexity. - Guy Blanc; Caleb Koch 001; Carmen Strassle; Li-Yang Tan (CCC, 2024)

Superconstant Inapproximability of Decision Tree Learning. - Caleb Koch 001; Carmen Strassle; Li-Yang Tan (COLT, 2024)

Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems. - Caleb Koch 001; Carmen Strassle; Li-Yang Tan (FOCS, 2024)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem. - Guy Blanc; Alexandre Hayderi; Caleb Koch 001; Li-Yang Tan (FOCS, 2024)

A Distributional-Lifting Theorem for PAC Learning. - Guy Blanc; Jane Lange; Carmen Strassle; Li-Yang Tan (COLT, 2025)

Computational-Statistical Tradeoffs from NP-hardness. - Guy Blanc; Caleb Koch 001; Carmen Strassle; Li-Yang Tan (CoRR, 2025)