Oliveira, Igor C. Carboni ;
Santhanam, Rahul
Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness
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 nvariable Ccircuits 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 subexponential time learning with membership queries, subexponential time learning with membership and equivalence queries, probabilistic function compression and probabilistic averagecase function compression.
A Dichotomy between Learnability and Pseudorandomness: In the nonuniform setting, there is nontrivial 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, (depthd)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 (depthd)C[n^k]. If for some epsilon > 0 there are Pnatural proofs useful against C[2^{n^{epsilon}}], then ZPEXP is not contained in C[poly(n)].
KarpLipton 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 nonuniform NC^1 reduce to the Minimum Circuit Size Problem via truthtable 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:118:49},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7532},
URN = {urn:nbn:de:0030drops75327},
doi = {10.4230/LIPIcs.CCC.2017.18},
annote = {Keywords: boolean circuits, learning theory, pseudorandomness}
}
01.08.2017
Keywords: 

boolean circuits, learning theory, pseudorandomness 
Seminar: 

32nd Computational Complexity Conference (CCC 2017)

Issue date: 

2017 
Date of publication: 

01.08.2017 