NDLI: On the Complexity of Hardness Amplification

Content Provider	IEEE Xplore Digital Library
Author	Chi-Jen Lu Shi-Chun Tsai Hsin-Lung Wu
Copyright Year	1963
Abstract	For deltaisin(0,1) and k,n isinN, we study the task of transforming a hard function f: {0,1}nrarr {0,1}, with which any small circuit disagrees on (1-delta)/2 fraction of the input, into a harder function f', with which any small circuit disagrees on (1-deltak)/2 fraction of the input. First, we show that such hardness amplification, when carried out in some black-box way, must require a high complexity. In particular, it cannot be realized by a circuit of depth d and size 2o(k ^1/d) or by a nondeterministic circuit of size o(k/logk) (and arbitrary depth) for any deltaisin(0,1). This extends the result of Viola, which only works when (1-delta)/2 is small enough. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently nonuniform in the following sense. To guarantee the hardness of the resulting function f', even against uniform machines, one has to start with a function f, which is hard against nonuniform algorithms with Omega(klog(1/delta)) bits of advice. This extends the result of Trevisan and Vadhan, which only addresses the case with (1-delta)/2=2^- n. Finally, we derive similar lower bounds for any black-box construction of a pseudorandom generator (PRG) from a hard function. To prove our results, we link the task of hardness amplifications and PRG constructions, respectively, to some type of error-reduction codes, and then we establish lower bounds for such codes, which we hope could find interest in both coding theory and complexity theory.
Sponsorship	IEEE Information Theory Society
Starting Page	4575
Ending Page	4586
Page Count	12
File Size	384721
File Format	PDF
ISSN	00189448
Volume Number	54
Issue Number	10
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-10-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Circuits Computer science Polynomials Contracts Boolean functions Codes Complexity theory Computational complexity Information science Cryptography pseudorandom generator hardness amplification list-decodable code
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

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

The Existence of Concatenated Codes List-Decodable up to the Hamming Bound

Soft Decoding, Dual BCH Codes, and Better List-Decodable $varepsilon$-Biased Codes

Cubic Boolean functions with highest resiliency

Analysis and Construction of Correctors

On Rational Interpolation-Based List-Decoding and List-Decoding Binary Goppa Codes

Recursive Lower Bounds on the Nonlinearity Profile of Boolean Functions and Their Applications

Linear-time encodable and decodable error-correcting codes

Comments on Constructions of Cryptographically Significant Boolean Functions Using Primitive Polynomials

Vectorial Bent Functions From Multiple Terms Trace Functions

On the Complexity of Hardness Amplification

Similar Documents

The Existence of Concatenated Codes List-Decodable up to the Hamming Bound

Soft Decoding, Dual BCH Codes, and Better List-Decodable $varepsilon$-Biased Codes

Cubic Boolean functions with highest resiliency

Analysis and Construction of Correctors

On Rational Interpolation-Based List-Decoding and List-Decoding Binary Goppa Codes

Recursive Lower Bounds on the Nonlinearity Profile of Boolean Functions and Their Applications

Linear-time encodable and decodable error-correcting codes

Comments on Constructions of Cryptographically Significant Boolean Functions Using Primitive Polynomials

Vectorial Bent Functions From Multiple Terms Trace Functions

On the Complexity of Hardness Amplification