Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems
Caleb Koch, Carmen Strassle, Li-Yang Tan
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
author order is alphabetical