Improved hardness amplification in NP

We study the problem of hardness amplification in NP . We prove that if there is a balanced function in NP such that any circuit of size s ( n ) = 2 Ω ( n ) fails to compute it on a 1 / poly ( n ) fraction of inputs, then there is a function in NP such that any circuit of size s ′ ( n ) fails to com...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2007-02, Vol.370 (1), p.293-298
Main Authors: Lu, Chi-Jen, Tsai, Shi-Chun, Wu, Hsin-Lung
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computational complexity
Computer science
control theory
systems
Exact sciences and technology
Hardness amplification
Mathematics
Numerical analysis
Numerical analysis. Scientific computation
Numerical methods in probability and statistics
Pseudorandom generator
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the problem of hardness amplification in NP . We prove that if there is a balanced function in NP such that any circuit of size s ( n ) = 2 Ω ( n ) fails to compute it on a 1 / poly ( n ) fraction of inputs, then there is a function in NP such that any circuit of size s ′ ( n ) fails to compute it on a 1 / 2 − 1 / s ′ ( n ) fraction of inputs, with s ′ ( n ) = 2 Ω ( n 2 / 3 ) . This improves the result of Healy et al. (STOC’04), which only achieves s ′ ( n ) = 2 Ω ( n 1 / 2 ) for the case with s ( n ) = 2 Ω ( n ) .
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2006.10.009