research
∙
07/09/2023
Properly Learning Decision Trees with Queries Is NP-Hard
We prove that it is NP-hard to properly PAC learn decision trees with qu...
share
research
∙
07/08/2023
A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers
We prove a strong composition theorem for junta complexity and show how ...
research
∙
11/04/2022
Certification with an NP Oracle
In the certification problem, the algorithm is given a function f with c...
research
∙
10/12/2022