文章基本信息

标题：Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
本地全文：下载
作者：Sergei Artemenko ; Ronen Shaltiel
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 12+\eps fraction of inputs. All hardness amplification results in the literature suffer from ``size loss'' meaning that s\epss. 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() such that when given oracle access to any function D that computes Amp(f) correctly on a 12+\eps fraction of inputs, RD computes f correctly on a 1− fraction of inputs. A \emph{non-uniform} reduction is allowed to also receive a short advice string 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 (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.
关键词：Black-box reductions, hardness amplification