Li-Yang Tan

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Superconstant Inapproximability of Decision Tree Learning.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

A Strong Direct Sum Theorem for Distributional Query Complexity.

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Lifting Uniform Learners via Distributional Decomposition.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Superpolynomial lower bounds for decision tree learning and testing.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Single-Pass Streaming Algorithms for Correlation Clustering.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Harnessing the power of choices in decision tree learning.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Certification with an NP Oracle.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Properly learning decision trees with queries is NP-hard.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

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

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Multitask Learning via Shared Features: Algorithms and Hardness.

[BibT_eX]

[DOI]

Konstantina Bairaktari

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas.

[BibT_eX]

[DOI]

Adv. Math. Commun., 2022

Properly Learning Decision Trees in almost Polynomial Time.

[BibT_eX]

[DOI]

J. ACM, 2022

Open Problem: Properly learning decision trees in polynomial time?

[BibT_eX]

[DOI]

CoRR, 2022

The query complexity of certification.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

A Generalization of the Satisfiability Coding Lemma and Its Applications.

[BibT_eX]

[DOI]

Milan Mossé

Harry Sha

Proceedings of the 25th International Conference on Theory and Applications of Satisfiability Testing, 2022

Popular decision tree algorithms are provably noise tolerant.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

A query-optimal algorithm for finding counterfactuals.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

Reconstructing Decision Trees.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Almost 3-Approximate Correlation Clustering in Constant Rounds.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

On the power of adaptivity in statistical adversaries.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

The Composition Complexity of Majority.

[BibT_eX]

[DOI]

Victor Lecomte

Prasanna Ramakrishnan

Proceedings of the 37th Computational Complexity Conference, 2022

2021

On the Power and Limitations of Branch and Cut.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Fooling Gaussian PTFs via Local Hyperconcentration.

[BibT_eX]

[DOI]

CoRR, 2021

Query strategies for priced information, revisited.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity.

[BibT_eX]

[DOI]

Moses Charikar

Weiyun Ma

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

Provably efficient, succinct, and precise explanations.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Learning Stochastic Decision Trees.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Tradeoffs for small-depth Frege proofs.

[BibT_eX]

[DOI]

Toniann Pitassi

Prasanna Ramakrishnan

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Sharper bounds on the Fourier concentration of DNFs.

[BibT_eX]

[DOI]

Victor Lecomte

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

Decision Tree Heuristics Can Fail, Even in the Smoothed Setting.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

The Power of Many Samples in Query Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Non-Malleability against Polynomial Tampering.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Testing and reconstruction via decision trees.

[BibT_eX]

[DOI]

CoRR, 2020

New lower bounds for Massively Parallel Computation from query complexity.

[BibT_eX]

[DOI]

Moses Charikar

Weiyun Ma

CoRR, 2020

Fooling Gaussian PTFs via local hyperconcentration.

[BibT_eX]

[DOI]

Ryan O'Donnell

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Unconditional Lower Bounds for Adaptive Massively Parallel Computation.

[BibT_eX]

[DOI]

Moses Charikar

Weiyun Ma

Proceedings of the SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020

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

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Estimating decision tree learnability with polylogarithmic sample complexity.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Provable guarantees for decision tree induction: the agnostic setting.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

2019

Top-down induction of decision trees: rigorous guarantees and inherent limitations.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Constructive derandomization of query algorithms.

[BibT_eX]

[DOI]

CoRR, 2019

Pseudorandomness for read-k DNF formulas.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Fooling Polytopes.

[BibT_eX]

[DOI]

Ryan O'Donnell

Electron. Colloquium Comput. Complex., 2018

Non-Malleable Codes for Small-Depth Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

An Average-Case Depth Hierarchy Theorem for Boolean Circuits.

[BibT_eX]

[DOI]

J. ACM, 2017

Settling the query complexity of non-adaptive junta testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

What Circuit Classes Can Be Learned with Non-Trivial Savings?.

[BibT_eX]

[DOI]

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Fooling Intersections of Low-Weight Halfspaces.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

2016

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

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

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

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles, and Boolean Circuits.

[BibT_eX]

[DOI]

Benjamin Rossman

SIGACT News, 2015

Approximating Boolean Functions with Depth-2 Circuits.

[BibT_eX]

[DOI]

SIAM J. Comput., 2015

An average-case depth hierarchy theorem for Boolean circuits.

[BibT_eX]

[DOI]

Benjamin Rossman

Electron. Colloquium Comput. Complex., 2015

An inequality for the Fourier spectrum of parity decision trees.

[BibT_eX]

[DOI]

Andrew Wan

CoRR, 2015

Noise Stable Halfspaces are Close to Very Small Juntas.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2015

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

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Approximate resilience, monotonicity, and the complexity of agnostic learning.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Algorithmic Signaling of Features in Auction Design.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory - 8th International Symposium, 2015

Adaptivity Helps for Testing Juntas.

[BibT_eX]

[DOI]

John Wright

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Analytic Methods in Concrete Complexity.

[BibT_eX]

[DOI]

PhD thesis, 2014

New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2014

A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Theory Comput., 2014

Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Learning circuits with few negations.

[BibT_eX]

[DOI]

Clément L. Canonne

Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2014

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

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

On DNF Approximators for Monotone Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

New Algorithms and Lower Bounds for Monotonicity Testing.

[BibT_eX]

[DOI]

Xi Chen

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

A Composition Theorem for Parity Kill Number.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Hypercontractivity Via the Entropy Method.

[BibT_eX]

[DOI]

Theory Comput., 2013

A Composition Theorem for the Fourier Entropy-Influence Conjecture.

[BibT_eX]

[DOI]

Ryan O'Donnell

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Learning Sums of Independent Integer Random Variables.

[BibT_eX]

[DOI]

Constantinos Daskalakis

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

On the Average Sensitivity and Density of k-CNF Formulas.

[BibT_eX]

[DOI]

Dominik Scheder

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Justin Thaler

Electron. Colloquium Comput. Complex., 2012

Hypercontractive inequalities via SOS, with an application to Vertex-Cover

[BibT_eX]

[DOI]

CoRR, 2012

Analysis of Boolean Functions

[BibT_eX]

[DOI]

CoRR, 2012

On the Distribution of the Fourier Spectrum of Halfspaces

[BibT_eX]

[DOI]

CoRR, 2012

2010

Bounding the average sensitivity and noise sensitivity of polynomial threshold functions.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

2005

The Algebra of Equality Proofs.

[BibT_eX]

[DOI]

Aaron Stump