Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with non-trivial learning:
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 >>>

TR17-173 | 6th November 2017
Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam

An Average-Case Lower Bound against ACC^0

In a seminal work, Williams [Wil14] showed that NEXP (non-deterministic exponential time) does not have polynomial-size ACC^0 circuits. Williams' technique inherently gives a worst-case lower bound, and until now, no average-case version of his result was known.

We show that there is a language L in NEXP (resp. EXP^NP) ... more >>>

ISSN 1433-8092 | Imprint