- 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 n-variable C-circuits 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 sub-exponential time settings, such as learning with membership queries, learning with membership and equivalence queries, and the related framework of truth-table compression. 3.(Learning versus Pseudorandom Functions) In the non-uniform setting, there is non-trivial 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 P-natural 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 hardness-randomness tradeoffs of [Impagliazzo-Wigderson, Trevisan-Vadhan], the easy witness method of [Kabanets, Impagliazzo-Kabanets-Wigderson], the interpretation of the Nisan-Wigderson generator as a pseudo-random function generator due to [Carmosino-Impagliazzo-Kabanets-Kolokolova] and the approximate min-max theorem of [Althofer, Lipton-Young]. 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 |
2016-09-08T11: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 n-variable C-circuits 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
sub-exponential time settings, such as learning with membership queries,
learning with membership and equivalence queries, and the related framework of
truth-table compression.
3.(Learning versus Pseudorandom Functions) In the non-uniform setting, there is
non-trivial 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 P-natural 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 hardness-randomness tradeoffs
of [Impagliazzo-Wigderson, Trevisan-Vadhan], the easy witness method of
[Kabanets, Impagliazzo-Kabanets-Wigderson], the interpretation of the
Nisan-Wigderson generator as a pseudo-random function generator due to
[Carmosino-Impagliazzo-Kabanets-Kolokolova] and the approximate min-max theorem
of [Althofer, Lipton-Young].
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 |
2017-03-10
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 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
Attribution-NonCommercial-NoDerivatives 4.0 International