Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity
复制标题
迈向 KRW 组成猜想：通过通信复杂性得出三次公式下界
DOI：
10.1007/s00037-017-0159-x
复制
发表时间：
2016
影响因子：
1.4
通讯作者：
Or Meir
中科院分区：
文献类型：
--
作者：
Irit Dinur;Or Meir
电路复杂性研究的主要挑战之一是证明德摩根公式的超多项式下界。Karchmer等人。(COMPUT Complex 5(3/4)：191-204,1995b)建议通过证明公式复杂性对于函数的组成f⋄g\DocumentClass[12pt]{Minimum}\usepackage{amsath}\usepackage{amsFonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{matrsfs}\usepackage{upgreek}\setLong{\oddsidemarin}{-69pt}\Begin{Document}$${f\g}$\end{Document}的组合而言，建议解决这个问题。他们表明，如果这个猜想被证明，将蕴含超多项式公式下界。证明KRW猜想的第一步是Edmonds等人。(Comput Complex 10(3)：210-246,2001)，他证明了构成“宇宙关系”的猜想的类比。在这项工作中，我们推广了Edmonds等人的论点。(2001)进一步到f⋄g\DocumentClass[12pt]{Minimum}\usepackage{amsath}\usepackage{amsFonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathsfs}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$${f\g}$\end{Document}，其中f是任意函数，g是奇偶函数。虽然KRW猜想的这一特殊情况已经在Hçstad关于随机限制的工作中得到了隐含的证明(Hçstad in SIAM J Comput27(1)：48-，1998)，但我们的证明似乎更有可能推广到该猜想的其他情况。特别地，我们的证明使用了一种完全不同的方法，基于Karchmer和Wigderson在(SIAM J离散数学3(2)：255-265,1990)中的通信复杂性技术。此外，我们的证明还给出了一个新的结构结果，粗略地说，计算f⋄g\DocumentClass[12pt]{Minimum}\usepackage{amsmath}\usepackage{waysym}\usepackage{amsfonts}\usepackage{amsbsy}\usepackage{amsbsy}\usepackage{mathsfs}\usepackage{upgreek}\setlong{oddsidemargin}{-69pt}\Begin{Document}${f\g}$\end{Document}的简单方法是唯一最优的方法。在此过程中，我们得到了最新的公式n3-o(1)的下界的一个新的证明，这是由于H&stad(1998)。
One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de Morgan formulas. Karchmer et al. (Comput Complex 5(3/4):191–204, 1995b) suggested to approach this problem by proving that formula complexity behaves “as expected” with respect to the composition of functions f⋄g\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${f\diamond g}$$\end{document} . They showed that this conjecture, if proved, would imply super-polynomial formula lower bounds. The first step toward proving the KRW conjecture was made by Edmonds et al. (Comput Complex 10(3):210–246, 2001), who proved an analogue of the conjecture for the composition of “universal relations.” In this work, we extend the argument of Edmonds et al. (2001) further to f⋄g\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${f\diamond g}$$\end{document} where f is an arbitrary function and g is the parity function. While this special case of the KRW conjecture was already proved implicitly in Håstad’s work on random restrictions (Håstad in SIAM J Comput 27(1):48–64, 1998), our proof seems more likely to be generalizable to other cases of the conjecture. In particular, our proof uses an entirely different approach, based on communication complexity technique of Karchmer & Wigderson in (SIAM J Discrete Math 3(2):255–265, 1990). In addition, our proof gives a new structural result, which roughly says that the naive way for computing f⋄g\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${f\diamond g}$$\end{document} is the only optimal way. Along the way, we obtain a new proof of the state-of-the-art formula lower bound of n3-o(1) due to Håstad (1998).