When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2017.18
URN: urn:nbn:de:0030-drops-75327
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7532/
 Go to the corresponding LIPIcs Volume Portal

### Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness

 pdf-format:

### Abstract

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 <= s(n). We show: Learning Speedups: If C[s(n)] admits a randomized weak learning algorithm under the uniform distribution with membership queries that runs in time 2^n/n^{\omega(1)}, then for every k >= 1 and epsilon > 0 the class C[n^k] can be learned to high accuracy in time O(2^{n^epsilon}). There is epsilon > 0 such that C[2^{n^{epsilon}}] can be learned in time 2^n/n^{omega(1)} if and only if C[poly(n)] can be learned in time 2^{(log(n))^{O(1)}}. Equivalences between Learning Models: We use learning speedups to obtain equivalences between various randomized learning and compression models, including sub-exponential time learning with membership queries, sub-exponential time learning with membership and equivalence queries, probabilistic function compression and probabilistic average-case function compression. A Dichotomy between Learnability and Pseudorandomness: In the non-uniform setting, there is non-trivial learning for C[poly(n)] if and only if there are no exponentially secure pseudorandom functions computable in C[poly(n)]. Lower Bounds from Nontrivial Learning: If for each k >= 1, (depth-d)-C[n^k] admits a randomized weak learning algorithm with membership queries under the uniform distribution that runs in time 2^n/n^{\omega(1)}, then for each k >= 1, BPE is not contained in (depth-d)-C[n^k]. If for some epsilon > 0 there are P-natural proofs useful against C[2^{n^{epsilon}}], then ZPEXP is not contained in C[poly(n)]. Karp-Lipton Theorems for Probabilistic Classes: If there is a k > 0 such that BPE is contained in i.o.Circuit[n^k], then BPEXP is contained in i.o.EXP/O(log(n)). If ZPEXP is contained in i.o.Circuit[2^{n/3}], then ZPEXP is contained in i.o.ESUBEXP. Hardness Results for MCSP: All functions in non-uniform NC^1 reduce to the Minimum Circuit Size Problem via truth-table reductions computable by TC^0 circuits. In particular, if MCSP is in TC^0 then NC^1 = TC^0.

### BibTeX - Entry

@InProceedings{oliveira_et_al:LIPIcs:2017:7532,
author =	{Igor C. Carboni Oliveira and Rahul Santhanam},
title =	{{Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness}},
booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
pages =	{18:1--18:49},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-040-8},
ISSN =	{1868-8969},
year =	{2017},
volume =	{79},
editor =	{Ryan O'Donnell},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},