Algorithms from Natural Lower Bounds
Algorithms from Natural Lower Bounds
复制标题
来自自然下界的算法
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Kolokolova
中科院分区：
文献类型：
--
作者：
M. Carmosino;R. Impagliazzo;Valentine Kabanets;A. Kolokolova
电路分析算法，如学习，SAT，最小电路尺寸和压缩意味着电路下限。我们显示了一个通用的含义在相反的方向：自然属性（在这个意义上的Razborov和Rudich）意味着随机学习和压缩算法。这是在去随机化背景之外的第一个这样的含义。作为一个应用，我们使用已知的AC[p]电路的自然下界（由于Razborov和Smolensky），以获得第一个准多项式时间算法，用于学习AC[p]函数，在PAC模型中均匀分布，具有成员查询。这项工作得到了西蒙斯基金会和NSF赠款#CNS-1523467和CCF-121351（M。卡莫西诺河Impagliazzo）和NSERC发现赠款（V. Kabanets，A. Kolokolova）。这项工作的一部分，而所有作者都访问西蒙斯研究所的理论计算。†Department of Computer Science，University of加州San Diego，拉霍亚，CA; mcarmosi@eng.ucsd.edu <$Department of Computer Science，University of加州San Diego，拉霍亚，CA; russell@cs.ucsd.edu §School of Computing Science，Simon Fraser University，Burnaby，BC，Canada; kabanets@cs.sfu.ca <$Department of Computer Science，Memorial University of Newfoundland，圣约翰，NL，Canada; kol@mun.ca
Circuit analysis algorithms such as learning, SAT, minimum circuit size, and compression imply circuit lower bounds. We show a generic implication in the opposite direction: natural properties (in the sense of Razborov and Rudich) imply randomized learning and compression algorithms. This is the first such implication outside of the derandomization setting. As an application, we use known natural lower bounds for AC[p] circuits (due to Razborov and Smolensky) to get the first quasi-polynomial time algorithm for learning AC[p] functions, in the PAC model over the uniform distribution, with membership queries. ∗This work was partially supported by the Simons Foundation and NSF grants #CNS-1523467 and CCF-121351 (M. Carmosino, R. Impagliazzo) and by NSERC Discovery grants (V. Kabanets, A. Kolokolova). This work was done in part while all authors were visiting Simons Institute for the Theory of Computing. †Department of Computer Science, University of California San Diego, La Jolla, CA; mcarmosi@eng.ucsd.edu ‡Department of Computer Science, University of California San Diego, La Jolla, CA; russell@cs.ucsd.edu §School of Computing Science, Simon Fraser University, Burnaby, BC, Canada; kabanets@cs.sfu.ca ¶Department of Computer Science, Memorial University of Newfoundland, St. John’s, NL, Canada; kol@mun.ca