Communication lower bounds via critical block sensitivity
Communication lower bounds via critical block sensitivity
复制标题
DOI：
10.1145/2591796.2591838
复制
发表时间：
2013-11
期刊：
影响因子：
--
通讯作者：
Mika Göös;T. Pitassi
中科院分区：
文献类型：
--
作者：
Mika Göös;T. Pitassi
我们使用Huynh和Nordström（STOC 2012）引入的一种新的复杂性度量--临界块敏感性来研究搜索问题的通信复杂性。开始，我们给出了Huynh和Nordström的以下中心结果的一个简单的新证明：如果S是一个具有临界块灵敏度B的搜索问题，则每个解决S的某个双方提升的随机双方协议需要Ω（B）位的通信。除了简单，我们的证明具有推广到多方设置的优点。我们联合收割机结合这些结果与新的临界块灵敏度下界Tseitin和卵石搜索问题，以获得以下应用。·单调电路深度：我们展示了一个关于n个变量的单调函数，其单调回路需要深度Ω（n/log n）;以前，Ω（n）的界是已知的（Raz and Wigderson，JACM 1992）。此外，我们证明了单调P中函数的一个紧θ（θ n）单调深度界。这意味着单调P中的平均情况层次定理类似于Filmus等人的结果。（FOCS 2013）。·证明复杂性：我们证明了新的秩下界以及获得的第一长度-空间下界的半代数证明系统，包括Lovász-Schrijver和拉瑟尔（SOS）系统。特别是，这些结果扩展和简化了Beame等人（SICOMP 2007）以及Huynh和Nordström的工作。
We use critical block sensitivity, a new complexity measure introduced by Huynh and Nordström (STOC 2012), to study the communication complexity of search problems. To begin, we give a simple new proof of the following central result of Huynh and Nordström: if S is a search problem with critical block sensitivity b, then every randomised two-party protocol solving a certain two-party lift of S requires Ω(b) bits of communication. Besides simplicity, our proof has the advantage of generalising to the multi-party setting. We combine these results with new critical block sensitivity lower bounds for Tseitin and Pebbling search problems to obtain the following applications. • Monotone circuit depth: We exhibit a monotone function on n variables whose monotone circuits require depth Ω(n/log n); previously, a bound of Ω(√n was known (Raz and Wigderson, JACM 1992). Moreover, we prove a tight Θ(√n) monotone depth bound for a function in monotone P. This implies an average-case hierarchy theorem within monotone P similar to a result of Filmus et al. (FOCS 2013). • Proof complexity: We prove new rank lower bounds as well as obtain the first length--space lower bounds for semi-algebraic proof systems, including Lovász--Schrijver and Lasserre (SOS) systems. In particular, these results extend and simplify the works of Beame et al. (SICOMP 2007) and Huynh and Nordström.