NDLI: On Basing Lower-Bounds for Learning on Worst-Case Assumptions

Content Provider	IEEE Xplore Digital Library
Author	Applebaum, B. Barak, B. Xiao, D.
Copyright Year	2008
Description	Author affiliation: Dept. of Comput. Sci., Princeton Univ., Princeton, NJ (Applebaum, B.; Barak, B.; Xiao, D.)
Abstract	We consider the question of whether P ne NP implies that there exists some concept class that is efficientlyrepresentable but is still hard to learn in the PAC model of Valiant (CACM '84), where the learner is allowed to output any efficient hypothesis approximating the concept, including an "improper" hypothesis that is not itself in the concept class. We show that unless the polynomial hierarchy collapses, such a statement cannot be proven via a large class of reductions including Karp reductions, truth-table reductions, and a restricted form of non-adaptive Turing reductions. Also, a proof that uses a Turing reduction of constant levels of adaptivity would imply an important consequence in cryptography as it yields a transformation from any average-case hard problem in NP to a one-way function. Our results hold even in the stronger model of agnostic learning. These results are obtained by showing that lower bounds for improper learning are intimately related to the complexity of zero-knowledge arguments and to the existence of weak cryptographic primitives. In particular, we prove that if alanguage L reduces to the task of improper learning of circuits, then, depending on the type of the reduction in use, either (1) L has a statistical zero-knowledge argument system, or (2) the worst-case hardness of L implies the existence of a weak variant of one-way functions defined by Ostrovsky-Wigderson (ISTCS '93). Interestingly, we observe that the converse implication also holds. Namely, if (1) or (2) hold then the intractability of L implies that improper learning is hard.
Starting Page	211
Ending Page	220
File Size	325928
Page Count	10
File Format	PDF
ISBN	9780769534367
ISSN	02725428
DOI	10.1109/FOCS.2008.35
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-10-25
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Polynomials Computer science Cryptography Circuits Machinery
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On basing lower-bounds for learning on worst-case assumptions.

On Basing Lower-Bounds for Learning on Worst-Case Assumptions

Lower bounds for polynomial calculus: non-binomial case

Tight Lower Bounds on Worst-Case Guarantees for Zero-Shot Learning with Attributes

On Basing ZK ≠ BPP on the Hardness of PAC Learning

On worst-case to average-case reductions for NP problems

Worst Case Exponential Lower Bounds for Input Resolution with Paramodulation

Lower bounds on the efficiency of generic cryptographic constructions

Cryptography in NC/sup 0/

On Basing Lower-Bounds for Learning on Worst-Case Assumptions

Similar Documents

On basing lower-bounds for learning on worst-case assumptions.

On Basing Lower-Bounds for Learning on Worst-Case Assumptions

Lower bounds for polynomial calculus: non-binomial case

Tight Lower Bounds on Worst-Case Guarantees for Zero-Shot Learning with Attributes

On Basing ZK ≠ BPP on the Hardness of PAC Learning

On worst-case to average-case reductions for NP problems

Worst Case Exponential Lower Bounds for Input Resolution with Paramodulation

Lower bounds on the efficiency of generic cryptographic constructions

Cryptography in NC/sup 0/

On Basing Lower-Bounds for Learning on Worst-Case Assumptions