Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-016 | 27th June 2011 12:53

Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification

RSS-Feed




Revision #1
Authors: Sergei Artemenko, Ronen Shaltiel
Accepted on: 27th June 2011 12:53
Downloads: 2582
Keywords: 


Abstract:

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.


Paper:

TR11-016 | 7th February 2011 16:34

Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification





TR11-016
Authors: Sergei Artemenko, Ronen Shaltiel
Publication: 7th February 2011 16:35
Downloads: 2793
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint