Back to search

Boston University

On learning from lower bounds

Abstract

dc:description.abstract

We 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 × 6

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/53112

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Karchmer, Ari. On learning from lower bounds. doctoral thesis, Boston University, 2024. https://hdl.handle.net/2144/53112