Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification

Hardness amplification results show that for every function

f

there exists a function

Amp

(

f

) such that the following holds: if every circuit of size

s

computes

f

correctly on at most a 1 − 

δ

fraction of inputs, then every circuit of size

s

′ computes

Amp

(

f

) correctly on at most a 1/2 + 

ε

fraction of inputs. All hardness amplification results in the literature suffer from “size loss” meaning that

s

′ ≤ 

ε

·

s

. In this paper we show that proofs using “non-uniform reductions” must suffer from size loss. To the best of our knowledge, all proofs in the literature are by non-uniform reductions. Our result is the first lower bound that applies to non-uniform reductions that are

adaptive

.

A reduction is an oracle circuit

R

(·)

such that when given oracle access to any function

D

that computes

Amp

(

f

) correctly on a 1/2 + 

ε

fraction of inputs,

R

D

computes

f

correctly on a 1 − 

δ

fraction of inputs. A

non-uniform

reduction is allowed to also receive a short advice string

α

that may depend on both

f

and

D

in an arbitrary way. The well known connection between hardness amplification and list-decodable error-correcting codes implies that reductions showing hardness amplification cannot be uniform for

ε

 < 1/4. A reduction is

non-adaptive

if it makes non-adaptive queries to its oracle. Shaltiel and Viola (STOC 2008) showed lower bounds on the number of queries made by non-uniform reductions that are

non-adaptive

. We show that every non-uniform reduction must make at least Ω(1/

ε

) queries to its oracle (even if the reduction is

adaptive

). This implies that proofs by non-uniform reductions must suffer from size loss.

We also prove the same lower bounds on the number of queries of non-uniform and adaptive reductions that are allowed to rely on arbitrary specific properties of the function

f

. Previous limitations on reductions were proven for “function-generic” hardness amplification, in which the non-uniform reduction needs to work for every function

f

and therefore cannot rely on specific properties of the function.