Learning from Nisan's natural proofs
Friday, March 22, 2024 - 10:30am to 12:00pm
Location:
G-882 Hewlett Room
Speaker:
Ari Karchmer (Boston University)
Seminar group:
In this talk, we will discuss the concept of Natural Proofs of circuit lower bounds (Razborov and Rudich, 1994), and their general relationship to cryptography and computational learning theory. Then, we will dive into some recent progress in the area by highlighting a new technique for extracting efficient distribution-independent learning algorithms or fully-agnostic learning algorithms from a restricted class of Natural Proofs due to Nisan (1993).
The new results presented in this talk are based in part on two papers:
- Ari Karchmer. Distributional pac-learning from nisan’s natural proofs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2024.
- Ari Karchmer. Agnostic membership query learning with nontrivial savings: New results, techniques. In 35th International Conference on Algorithmic Learning Theory (ALT 2024). PMLR, 2024.