Carmen Strassle

According to our database, Carmen Strassle authored at least 7 papers between 2023 and 2024.

Collaborative distances:

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

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

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