Caleb Koch

According to our database, Caleb Koch authored at least 18 papers between 2017 and 2026.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of four.

2026

Feature Selection and Junta Testing are Statistically Equivalent.

Lorenzo Beretta, Nathaniel Harms, Caleb Koch

Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, 2026

Samplability Makes Learning Easier.

Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan

Proceedings of the 17th Innovations in Theoretical Computer Science Conference, 2026

2025

The power of quantum circuits in sampling.

Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan

CoRR, October, 2025

Testing Juntas Optimally with Samples.

Lorenzo Beretta, Nathaniel Harms, Caleb Koch

CoRR, May, 2025

Computational-Statistical Tradeoffs from NP-hardness.

Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan

Proceedings of the 66th IEEE Annual Symposium on Foundations of Computer Science, 2025

2024

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

Guy Blanc, Alexandre Hayderi, Caleb Koch, Li-Yang Tan

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems.

Caleb Koch, Carmen Strassle, Li-Yang Tan

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Superconstant Inapproximability of Decision Tree Learning.

Caleb Koch, Carmen Strassle, Li-Yang Tan

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

A Strong Direct Sum Theorem for Distributional Query Complexity.

Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Automata Learning with an Incomplete Teacher (Artifact).

Mark Moeller, Thomas Wiener, Alaia Solko-Breslin, Caleb Koch, Nate Foster, Alexandra Silva

Dagstuhl Artifacts Ser., 2023

Superpolynomial lower bounds for decision tree learning and testing.

Caleb Koch, Carmen Strassle, Li-Yang Tan

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Certification with an NP Oracle.

Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Properly learning decision trees with queries is NP-hard.

Caleb Koch, Carmen Strassle, Li-Yang Tan

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

A strong composition theorem for junta complexity and the boosting of property testers.

Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Automata Learning with an Incomplete Teacher.

Mark Moeller, Thomas Wiener, Alaia Solko-Breslin, Caleb Koch, Nate Foster, Alexandra Silva

Proceedings of the 37th European Conference on Object-Oriented Programming, 2023

2022

The query complexity of certification.

Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

A query-optimal algorithm for finding counterfactuals.

Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan

Proceedings of the International Conference on Machine Learning, 2022

2017

Hyperprofile-Based Computation Offloading for Mobile Edge Networks.

Andrew Crutcher, Caleb Koch, Kyle Coleman, Jon Patman, Flavio Esposito, Prasad Calyam

Proceedings of the 14th IEEE International Conference on Mobile Ad Hoc and Sensor Systems, 2017