Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875472 | Theoretical Computer Science | 2018 | 23 Pages |
Abstract
An important open problem in computational complexity theory is to prove the size of circuits, namely, Boolean circuit lower bounds, necessary to solve explicit problems. We survey learning-theoretic approaches to proofs of Boolean circuit lower bounds in this paper. In particular, we discuss how to prove circuit lower bounds in uniform classes by assuming (or constructing) circuit-learning algorithms in several settings, such as the exact, probably approximately correct (PAC), and statistical query learning models.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Akinori Kawachi,