Mining Circuit Lower Bound Proofs for Meta-Algorithms
Mining Circuit Lower Bound Proofs for Meta-Algorithms
复制标题
元算法的挖矿电路下界证明
DOI：
--
复制
发表时间：
2014
影响因子：
1.4
通讯作者：
David Zuckerman
中科院分区：
文献类型：
--
作者：
Ruiwen Chen;Valentine Kabanets;A. Kolokolova;Ronen Shaltiel;David Zuckerman
我们证明，基于随机限制方法的电路下界证明为相应电路类的“简单”布尔函数产生了非平凡的压缩算法。压缩问题定义如下：给定一个 n 变量布尔函数 f 的真值表，该函数可由已知电路类别中的某个未知小电路计算，在确定性时间 poly(2n) 中找到计算 f 的电路 C（对 C 的类型没有限制），使得 C 的大小小于普通电路大小 2n/ndocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{文档}$${2^n/n}$$end{文档}。我们对可通过 AC0 电路、（德摩根）公式和大小已知相应电路类的下界的（一次读取）分支程序进行计算的函数进行了非平凡的压缩。这些压缩算法依赖于“简单”函数的结构特征，这对于证明电路下界和设计“元算法”（例如 Circuit-SAT）都很有用。对于 (de Morgan) 公式，此类结构表征由 Subbotovskaya (Doklady Akademii Nauk SSSR 136(3):553–555, 1961) 和 Håstad (SIAM J Comput 27:48–64, 1998) 的“随机限制下的收缩”结果提供，并由 Santhanam (Proceedings of the第五十届 IEEE 计算机科学基础研讨会，第 183-192 页，2010 年），Impagliazzo、Meka 和 Zuckerman（第 53 届 IEEE 计算机科学基础年度研讨会论文集，第 111-119 页，2012b）以及 Komargodski 和 Raz（第 53 届 IEEE 计算机科学基础研讨会论文集），以及 Komargodski 和 Raz（第 53 届 IEEE 计算机科学基础研讨会论文集）第四十五届 ACM 计算理论年度研讨会，第 171-180 页，2013 年）。我们为（德摩根）公式的收缩结果的“高概率”版本提供了一个新的、简单的证明，并改进了参数。我们使用这个收缩结果来获得大小约为 n2 的 (de Morgan) 公式的压缩和 #SAT 算法。我们还使用这个收缩结果来获得 Komargodski 和 Raz 的结果的替代证明（第四十五届 ACM 计算理论研讨会论文集，第 171-180 页，2013）针对小（德摩根）公式的平均情况下界。最后，我们证明了电路类 C⊆P/polydocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} 的任何非平凡压缩算法的存在egin{document}$${mathcal{C}subseteq mathsf{P}/ mathsf{poly}}$$end{document} 将暗示电路下界 NEXP⊈Cdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt}egin{文档}$${mathsf{NEXP}
ot subseteq mathcal{C}}$$end{文档} ; Williams 也独立证明了类似的含义（第四十五届 ACM 计算理论研讨会论文集，第 21-30 页，2013 年）。这补充了 Williams 的结果（第四十二届年度 ACM 计算理论研讨会论文集，第 231-240 页，2010 年），即电路类 Cdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} 的任何非平凡 Circuit-SAT 算法usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${mathcal{C}}$$end{document} 暗示针对 Cdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} 的超多项式下界usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${mathcal{C}}$$end{document} 用于 NEXP 中的语言。
We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for “easy” Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an n-variate Boolean function f computable by some unknown small circuit from a known class of circuits, find in deterministic time poly(2n) a circuit C (no restriction on the type of C) computing f so that the size of C is less than the trivial circuit size 2n/ndocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${2^n/n}$$end{document}. We get non-trivial compression for functions computable by AC0 circuits, (de Morgan) formulas, and (read-once) branching programs of the size for which the lower bounds for the corresponding circuit class are known. These compression algorithms rely on the structural characterizations of “easy” functions, which are useful both for proving circuit lower bounds and for designing “meta-algorithms” (such as Circuit-SAT). For (de Morgan) formulas, such structural characterization is provided by the “shrinkage under random restrictions” results by Subbotovskaya (Doklady Akademii Nauk SSSR 136(3):553–555, 1961) and Håstad (SIAM J Comput 27:48–64, 1998), strengthened to the “high-probability” version by Santhanam (Proceedings of the Fifty-First Annual IEEE Symposium on Foundations of Computer Science, pp 183–192, 2010), Impagliazzo, Meka & Zuckerman (Proceedings of the Fifty-Third Annual IEEE Symposium on Foundations of Computer Science, pp 111–119, 2012b), and Komargodski & Raz (Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp 171–180, 2013). We give a new, simple proof of the “high-probability” version of the shrinkage result for (de Morgan) formulas, with improved parameters. We use this shrinkage result to get both compression and #SAT algorithms for (de Morgan) formulas of size about n2. We also use this shrinkage result to get an alternative proof of the result by Komargodski & Raz (Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp 171–180, 2013) of the average-case lower bound against small (de Morgan) formulas. Finally, we show that the existence of any non-trivial compression algorithm for a circuit class C⊆P/polydocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${mathcal{C} subseteq mathsf{P}/ mathsf{poly}}$$end{document} would imply the circuit lower bound NEXP⊈Cdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${mathsf{NEXP}
ot subseteq mathcal{C}}$$end{document} ; a similar implication is independently proved also by Williams (Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp 21–30, 2013). This complements the result by Williams (Proceedings of the Forty-Second Annual ACM Symposium on Theory of Computing, pp 231–240, 2010) that any non-trivial Circuit-SAT algorithm for a circuit class Cdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${mathcal{C}}$$end{document} would imply a superpolynomial lower bound against Cdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${mathcal{C}}$$end{document} for a language in NEXP.