Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
复制标题
非均匀和自适应降低的查询复杂性下限显示难度放大
DOI：
10.1007/s00037-012-0056-2
复制
发表时间：
2011
影响因子：
1.4
通讯作者：
Ronen Shaltiel
中科院分区：
文献类型：
--
作者：
Sergei Artemenko;Ronen Shaltiel
硬度放大结果表明，对于每个布尔函数f，存在一个布尔函数amp（f），因此，如果每个大小s电路最多在1 -δ输入的最多计算f，则每个大小s'电路都会计算放大器（ f）最多正确地a $$ {1/2+\ epsilon} $$输入的分数。 } $$使用“不均匀减少”的证据必须遭受这样的尺寸损失。降低是Oracle电路$$ {r^{（\ cdot）}}} $$，它可以将Oracle访问到计算AMP（F）的任何功能D正确地，在A $$ {1/2+\ epsilon} $$输入的分数上，在1-Δ的输入分数上正确地计算F。 F和D。硬度之间众所周知的联系放大和列表可纠正的校正代码意味着显示硬度放大的减少不能统一，对于$$ {\ epsilon <1/4} $$，我们表明，每个非均匀降低都必须使至少$$ {\ omega（\ omega） 1/\ epsilon）} $$对其甲骨文的查询，这意味着我们的尺寸损失是适用于适应性的第一个下限，而Shaltiel＆Viola的先前界限（Sicomp） 2010）仅适用于非自适应减少。
Hardness amplification results show that for every Boolean function f, there exists a Boolean function Amp(f) such that if every size s circuit computes f correctly on at most a 1 − δ fraction of inputs, then every size s′ circuit computes Amp(f) correctly on at most a $${1/2+\epsilon}$$ fraction of inputs. All hardness amplification results in the literature suffer from “size loss” meaning that $${s' \leq \epsilon \cdot s}$$. We show that proofs using “non-uniform reductions” must suffer from such size loss.A reduction is an oracle circuit $${R^{(\cdot)}}$$ which given oracle access to any function D that computes Amp(f) correctly on a $${1/2+\epsilon}$$ fraction of inputs, 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. The well-known connection between hardness amplification and list-decodable error-correcting codes implies that reductions showing hardness amplification cannot be uniform for $${\epsilon < 1/4}$$. We show that every non-uniform reduction must make at least $${\Omega(1/\epsilon)}$$ queries to its oracle, which implies size loss. Our result is the first lower bound that applies to non-uniform reductions that are adaptive, whereas previous bounds by Shaltiel & Viola (SICOMP 2010) applied only to non-adaptive reductions. We also prove similar bounds for a stronger notion of “function-specific” reductions in which the reduction is only required to work for a specific function f.