Abstract
dc:description.abstractWe present results that complement and solidify known relationships between circuit lower bounds and algorithms for learning circuits. In particular, we present ways of converting Nisan's method of communication-complexity-based circuit lower bounds to algorithms for learning circuits with threshold gates. From this we obtain: A generic transformation of any circuit lower bound proved by Nisan's method into an efficient distributional PAC-learning algorithm. The distributional PAC-learning model is also a contribution of this thesis; the model arises naturally from Nisan's method, but remains independently motivated for future study. Generic transformations of circuit lower bounds proved by Nisan's method into nontrivial agnostic membership query learning algorithms, exact learning algorithms with membership and equivalence queries, and more. Our study of Nisan's method is guided by our observation that understanding the connection between Nisan's method and learning algorithms is central to understanding the furthest extent to which circuit lower bounds imply learning algorithms.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy
- Level thesis:degree_level
- doctoral
- Discipline thesis:degree_discipline
- Computer Science
- Grantor
- Boston University
- Year dc:date.issued
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Karchmer, Ari
- Advisor dc:contributor.advisor
-
- Canetti, Ran
Subjects
dc:subject × 6Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53112