Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Karp-Lipton theorems:
TR16-197 | 7th December 2016
Igor Carboni Oliveira, Rahul Santhanam

Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness

We prove several results giving new and stronger connections between learning theory, circuit complexity and pseudorandomness. Let C be any typical class of Boolean circuits, and C[s(n)] denote n-variable C-circuits of size at most s(n). We show:

Learning Speedups: If C[$n^{O(1)}$] admits a randomized weak learning algorithm under the uniform ... more >>>

ISSN 1433-8092 | Imprint