Papers

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