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-\delta$ fraction of inputs, then every circuit of size $s'$ computes $Amp(f)$ correctly on at most a $1/2+\eps$ fraction of inputs. All hardness amplification results in the literature suffer from ``size loss'' meaning that $s' \le \eps \cdot 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 \emph{adaptive}.

A reduction is an oracle circuit $R^{(\cdot)}$ such that when given oracle access to any function $D$ that computes $Amp(f)$ correctly on a $1/2+\eps$ fraction of inputs, $R^D$ computes $f$ correctly on a $1-\delta$ fraction of inputs. A \emph{non-uniform} reduction is allowed to also receive a short advice string $\alpha$ that may depend on both $f$ and $D$ in an arbitrary way. It is known that reductions showing hardness amplification must be non-uniform. A reduction is
\emph{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 \emph{non-adaptive}. We show that every non-uniform reduction must make at least $\Omega(1/\eps)$ queries to its oracle (even if the reduction is \emph{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.

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-\delta$ fraction of inputs, then every circuit of size $s'$ computes $Amp(f)$ correctly on at most a $1/2+\eps$ fraction of inputs. All hardness amplification results in the literature suffer from ``size loss'' meaning that $s' \le \eps \cdot 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 \emph{adaptive}.

A reduction is an oracle circuit $R^{(\cdot)}$ such that when given oracle access to any function $D$ that computes $Amp(f)$ correctly on a $1/2+\eps$ fraction of inputs, $R^D$ computes $f$ correctly on a $1-\delta$ fraction of inputs. A \emph{non-uniform} reduction is allowed to also receive a short advice string $\alpha$ that may depend on both $f$ and $D$ in an arbitrary way. It is known that reductions showing hardness amplification must be non-uniform. A reduction is
\emph{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 \emph{non-adaptive}. We show that every non-uniform reduction must make at least $\Omega(1/\eps)$ queries to its oracle (even if the reduction is \emph{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.