 Library Home /
 Search Collections /
 Open Collections /
 Browse Collections /
 BIRS Workshop Lecture Videos /
 Stronger Connections between Learning, Lower Bounds...
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Stronger Connections between Learning, Lower Bounds and Pseudorandomness Santhanam, Rahul
Description
We prove several results giving new and stronger connections between learning theory, circuit complexity and pseudorandomness, including: 1. (Learning Speedups) Let C be any "typical" class of Boolean circuits, and C[s(n)] denote nvariable Ccircuits of size at most s(n). If C[poly] 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 and \varepsilon > 0 the class C[n^k] can be learned to high accuracy in time O(2^{n^\varepsilon}). 2.(Equivalences) There is \varepsilon > 0 such that C[2^{n^{\varepsilon}}] can be learned in time 2^n/n^{\omega(1)} if and only if C[poly] can be learned in time 2^{O((\log n)^c)}. Furthermore, our proof technique yields equivalences between various randomized learning models in the exponential and subexponential time settings, such as learning with membership queries, learning with membership and equivalence queries, and the related framework of truthtable compression. 3.(Learning versus Pseudorandom Functions) In the nonuniform setting, there is nontrivial learning for C[poly(n)] if and only if there are no secure pseudorandom function families computable in C[poly]. 4.(Lower Bounds from Nontrivial Learning Algorithms) Let C be any class of Boolean circuits closed under projection. If for each k, 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, BPE is not contained in C[n^k]. If there are Pnatural proofs useful against C[2^{n^{o(1)}}], then ZPEXP is not contained in C[poly]. Among the proof techniques we use are the uniform hardnessrandomness tradeoffs of [ImpagliazzoWigderson, TrevisanVadhan], the easy witness method of [Kabanets, ImpagliazzoKabanetsWigderson], the interpretation of the NisanWigderson generator as a pseudorandom function generator due to [CarmosinoImpagliazzoKabanetsKolokolova] and the approximate minmax theorem of [Althofer, LiptonYoung]. This is joint work with Igor Carboni Oliveira.
Item Metadata
Title 
Stronger Connections between Learning, Lower Bounds and Pseudorandomness

Creator  
Publisher 
Banff International Research Station for Mathematical Innovation and Discovery

Date Issued 
20160908T11:09

Description 
We prove several results giving new and stronger connections between
learning theory, circuit complexity and pseudorandomness, including:
1. (Learning Speedups) Let C be any "typical" class of Boolean circuits, and
C[s(n)] denote nvariable Ccircuits of size at most s(n). If C[poly] 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 and
\varepsilon > 0 the class C[n^k] can be learned to high accuracy in time
O(2^{n^\varepsilon}).
2.(Equivalences) There is \varepsilon > 0 such that C[2^{n^{\varepsilon}}] can
be learned in time 2^n/n^{\omega(1)} if and only if C[poly] can be learned in
time 2^{O((\log n)^c)}. Furthermore, our proof technique yields equivalences
between various randomized learning models in the exponential and
subexponential time settings, such as learning with membership queries,
learning with membership and equivalence queries, and the related framework of
truthtable compression.
3.(Learning versus Pseudorandom Functions) In the nonuniform setting, there is
nontrivial learning for C[poly(n)] if and only if there are no secure
pseudorandom function families computable in C[poly].
4.(Lower Bounds from Nontrivial Learning Algorithms) Let C be any class of
Boolean circuits closed under projection. If for each k, 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, BPE is not
contained in C[n^k]. If there are Pnatural proofs useful against
C[2^{n^{o(1)}}], then ZPEXP is not contained in C[poly].
Among the proof techniques we use are the uniform hardnessrandomness tradeoffs
of [ImpagliazzoWigderson, TrevisanVadhan], the easy witness method of
[Kabanets, ImpagliazzoKabanetsWigderson], the interpretation of the
NisanWigderson generator as a pseudorandom function generator due to
[CarmosinoImpagliazzoKabanetsKolokolova] and the approximate minmax theorem
of [Althofer, LiptonYoung].
This is joint work with Igor Carboni Oliveira.

Extent 
44 minutes

Subject  
Type  
File Format 
video/mp4

Language 
eng

Notes 
Author affiliation: University of Oxford

Series  
Date Available 
20170310

Provider 
Vancouver : University of British Columbia Library

Rights 
AttributionNonCommercialNoDerivatives 4.0 International

DOI 
10.14288/1.0343130

URI  
Affiliation  
Peer Review Status 
Unreviewed

Scholarly Level 
Faculty

Rights URI  
Aggregated Source Repository 
DSpace

Item Media
Item Citations and Data
Rights
AttributionNonCommercialNoDerivatives 4.0 International