Guy Blanc

Gregory Valiant

CoRR, 2024

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

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 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

Subsampling Suffices for Adaptive Data Analysis.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 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

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

Properly Learning Decision Trees in almost Polynomial Time.

[BibT_eX]

[DOI]

J. ACM, 2022

New Near-Linear Time Decodable Codes Closer to the GV Bound.

[BibT_eX]

[DOI]

Dean Doron

Electron. Colloquium Comput. Complex., 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

Properly learning decision trees in almost polynomial time.

[BibT_eX]

[DOI]

Proceedings of the International Symposium on Artificial Intelligence and Mathematics 2022 (ISAIM 2022), 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

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

2021

Query strategies for priced information, revisited.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 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

Multiway Online Correlated Selection.

[BibT_eX]

[DOI]

Moses Charikar

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

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

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

Testing and reconstruction via decision trees.

[BibT_eX]

[DOI]

Panagiotis Angelikopoulos

CoRR, 2020

Efficient hyperparameter optimization by way of PAC-Bayes bound minimization.

[BibT_eX]

[DOI]

John J. Cherian

Andrew G. Taube

Robert T. McGibbon

CoRR, 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

Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 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

2018

Adaptive Sampled Softmax with Kernel Based Sampling.

[BibT_eX]

[DOI]