Caleb Koch

31 papers A* 10A 4B 1Journal 16
YearRankTypeTitle / Venue / Authors
2026 A* conf
Feature Selection and Junta Testing are Statistically Equivalent.
SODA
Lorenzo Beretta, Nathaniel Harms, Caleb Koch
2026 A conf
Samplability Makes Learning Easier.
ITCS
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan
2025 A* conf
Computational-Statistical Tradeoffs from NP-hardness.
FOCS
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
2025 J jnl
Computational-Statistical Tradeoffs from NP-hardness.
CoRR
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
2025 J jnl
Samplability makes learning easier.
CoRR
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan
2025 J jnl
Testing Juntas Optimally with Samples.
CoRR
Lorenzo Beretta, Nathaniel Harms, Caleb Koch
2025 J jnl
The power of quantum circuits in sampling.
CoRR
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan
2024 A conf
A Strong Direct Sum Theorem for Distributional Query Complexity.
CCC
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
2024 J jnl
A Strong Direct Sum Theorem for Distributional Query Complexity.
CoRR
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
2024 A* conf
Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems.
FOCS
Caleb Koch, Carmen Strassle, Li-Yang Tan
2024 J jnl
Fast decision tree learning solves hard coding-theoretic problems.
CoRR
Caleb Koch, Carmen Strassle, Li-Yang Tan
2024 A* conf
Superconstant Inapproximability of Decision Tree Learning.
COLT
Caleb Koch, Carmen Strassle, Li-Yang Tan
2024 J jnl
Superconstant Inapproximability of Decision Tree Learning.
CoRR
Caleb Koch, Carmen Strassle, Li-Yang Tan
2024 A* conf
The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem.
FOCS
Guy Blanc, Alexandre Hayderi, Caleb Koch, Li-Yang Tan
2024 J jnl
The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem.
CoRR
Guy Blanc, Alexandre Hayderi, Caleb Koch, Li-Yang Tan
2023 J jnl
A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers.
CoRR
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
2023 A* conf
A strong composition theorem for junta complexity and the boosting of property testers.
FOCS
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
2023 J jnl
Automata Learning with an Incomplete Teacher (Artifact).
Dagstuhl Artifacts Ser.
Mark Moeller, Thomas Wiener, Alaia Solko-Breslin, Caleb Koch, Nate Foster, Alexandra Silva
2023 A conf
Automata Learning with an Incomplete Teacher.
ECOOP
Mark Moeller, Thomas Wiener, Alaia Solko-Breslin, Caleb Koch, Nate Foster, Alexandra Silva
2023 A conf
Certification with an NP Oracle.
ITCS
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan
2023 J jnl
Properly Learning Decision Trees with Queries Is NP-Hard.
CoRR
Caleb Koch, Carmen Strassle, Li-Yang Tan
2023 A* conf
Properly learning decision trees with queries is NP-hard.
FOCS
Caleb Koch, Carmen Strassle, Li-Yang Tan
2023 A* conf
Superpolynomial lower bounds for decision tree learning and testing.
SODA
Caleb Koch, Carmen Strassle, Li-Yang Tan
2022 J jnl
A Query-Optimal Algorithm for Finding Counterfactuals.
CoRR
Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan
2022 A* conf
A query-optimal algorithm for finding counterfactuals.
ICML
Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan
2022 J jnl
Certification with an NP Oracle.
CoRR
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan
2022 J jnl
Superpolynomial Lower Bounds for Decision Tree Learning and Testing.
CoRR
Caleb Koch, Carmen Strassle, Li-Yang Tan
2022 J jnl
The Query Complexity of Certification.
CoRR
Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan
2022 A* conf
The query complexity of certification.
STOC
Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan
2017 B conf
Hyperprofile-Based Computation Offloading for Mobile Edge Networks.
MASS
Andrew Crutcher, Caleb Koch, Kyle Coleman, Jon Patman, Flavio Esposito, Prasad Calyam
2017 J jnl
Hyperprofile-based Computation Offloading for Mobile Edge Networks.
CoRR
Andrew Crutcher, Caleb Koch, Kyle Coleman, Jon Patman, Flavio Esposito, Prasad Calyam