The Power of Quantum Circuits in Sampling
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan
|
Manuscript |
Samplability Makes Learning Easier
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan
|
ITCS 26 |
Feature Selection and Junta Testing Are Statistically Equivalent
Lorenzo Beretta, Nathaniel Harms, Caleb Koch
|
SODA 26 |
Computational-Statistical Tradeoffs from NP-hardness
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
|
FOCS 25 |
Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems
Caleb Koch, Carmen Strassle, Li-Yang Tan
|
FOCS 24 |
The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
Guy Blanc, Alexandre Hayderi, Caleb Koch, Li-Yang Tan
Invited to FOCS 2024 special issue
Journal of the ACM, 2026
|
FOCS 24 |
A Strong Direct Sum Theorem for Distributional Query Complexity
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
Invited to CCC 2024 special issue
|
CCC 24 |
Superconstant Inapproximability of Decision Tree Learning
Caleb Koch, Carmen Strassle, Li-Yang Tan
|
COLT 24 |
A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
|
FOCS 23 |
Properly Learning Decision Trees with Queries Is NP-Hard
Caleb Koch, Carmen Strassle, Li-Yang Tan
|
FOCS 23 |
Superpolynomial Lower Bounds for Decision Tree Learning and Testing
Caleb Koch, Carmen Strassle, Li-Yang Tan
|
SODA 23 |
Certification with an NP Oracle
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan
|
ITCS 23 |
A Query-Optimal Algorithm for Finding Counterfactuals
Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan
|
ICML 22 |
The Query Complexity of Certification
Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan
|
STOC 22 |
