Conference item icon

Conference item

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 n-variable C-circuits of size ≤ s(n). We show: Learning Speedups. If C[poly(n)] admits a randomized weak learning algorithm under the uniform distribution with membership queries that runs in time 2n/nω(1), then for every k ≥ 1 and ε > 0 the class C[n k ] can be learned to high accuracy in time O(2n...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.CCC.2017.18

Authors


Oliveira, IC More by this author
More by this author
Department:
Magdalen College
More from this funder
Funding agency for:
Santhanam, R
Publisher:
Schloss Dagstuhl Publisher's website
Volume:
79
Pages:
18:1--18:49
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Publication date:
2017-07-21
Acceptance date:
2017-04-19
DOI:
ISSN:
1868-8969
Pubs id:
pubs:691585
URN:
uri:9aacd5da-210a-42d7-9fab-d91d8723a834
UUID:
uuid:9aacd5da-210a-42d7-9fab-d91d8723a834
Local pid:
pubs:691585
ISBN:
978-3-95977-040-8

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP