Hardness amplification proofs require majority

Hardness amplification is the fundamental task of converting a δ-hard function f : (0, 1) n -> (0, 1) into a (1/2-ε)-hard function Amp(f), where f is γ-hard if small circuits fail to compute f on at least a γ fraction of the inputs. Typically, ε,δ are small (and δ=2 -k captures the case where f is worst-case hard). Achieving ε = 1/n Ω(1) is a prerequisite for cryptography and most pseudorandom-generator constructions.

Authors

• Ronen Shaltiel
• Emanuele Viola

Keywords

• majority
• hardness
• average-case complexity
• constant-depth circuits
• amplification
• black-box
• natural proofs