Extended formulations, nonnegative factorizations, and randomized communication protocols
Extended formulations, nonnegative factorizations, and randomized communication protocols
复制标题
扩展公式、非负分解和随机通信协议
DOI：
10.1007/s10107-014-0755-3
复制
发表时间：
2015
影响因子：
2.7
通讯作者：
H.R. Tiwary
中科院分区：
文献类型：
--
作者：
Y. Faenza;S. Fiorini;R. Grappe;H.R. Tiwary
多面体的一种扩展形式是多面体的线性描述和线性映射，使得。这些对象在多面体组合学和优化理论中具有根本的重要性，并且是许多研究的主题。Yannakakis的因子分解定理（Yannakakis in J Comput Syst Sci 43（3）：441-466，1991）提供了扩展公式和通信复杂性之间令人惊讶的联系，表明扩展公式的最小大小等于其松弛矩阵的非负秩。此外，Yannakakis还证明了的非负秩最多为，这是任何确定性协议计算的复杂性。在本文中，我们表明，后者的结果可以加强时，我们允许协议berandomized。特别地，我们证明了任何非负矩阵的非负秩的底对数等于期望中计算矩阵的随机通信协议的最小复杂度。使用Yannakakis的因子分解定理，这意味着多面体扩展公式的最小尺寸的底对数等于计算期望的松弛矩阵的随机通信协议的最小复杂度。我们表明，允许随机化的协议可以是至关重要的，以获得小的扩展配方。具体来说，我们证明了，对于生成树和完美匹配的多面体，在协议中的小方差的力量在扩展配方的大尺寸。
An extended formulation of a polyhedronis a linear description of a polyhedrontogether with a linear mapsuch that. These objects are of fundamental importance in polyhedral combinatorics and optimization theory, and the subject of a number of studies. Yannakakis’ factorization theorem (Yannakakis in J Comput Syst Sci 43(3):441–466, 1991) provides a surprising connection between extended formulations and communication complexity, showing that the smallest size of an extended formulation ofequals the nonnegative rank of its slack matrix. Moreover, Yannakakis also shows that the nonnegative rank ofis at most, whereis the complexity of anydeterministicprotocol computing. In this paper, we show that the latter result can be strengthened when we allow protocols to berandomized. In particular, we prove that the base-logarithm of the nonnegative rank of any nonnegative matrix equals the minimum complexity of a randomized communication protocol computing the matrix in expectation. Using Yannakakis’ factorization theorem, this implies that the base-logarithm of the smallest size of an extended formulation of a polytopeequals the minimum complexity of a randomized communication protocol computing the slack matrix ofin expectation. We show that allowing randomization in the protocol can be crucial for obtaining small extended formulations. Specifically, we prove that for the spanning tree and perfect matching polytopes, small variance in the protocol forces large size in the extended formulation.
登录
查看更多内容
DOI：
10.1007/978-0-387-30162-4_28
发表时间：
2021-08
期刊：
Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97)
影响因子：
--
作者：
通讯作者：
--
几何参数为阈值电路和分布式计算提供了更好的界限
DOI：
10.1109/sct.1991.160275
发表时间：
1991
期刊：
[1991] Proceedings of the Sixth Annual Structure in Complexity Theory Conference
影响因子：
--
作者：
Matthias Krause
通讯作者：
Matthias Krause
对称性对于扩展配方的尺寸很重要
DOI：
--
发表时间：
2009
期刊：
Conference on Integer Programming and Combinatorial Optimization
影响因子：
--
作者：
V. Kaibel;Kanstantsin Pashkovich;D. Theis
通讯作者：
D. Theis
通过 Padberg-Rao 和紧凑线性程序分离无爪图中的稳定集
DOI：
--
发表时间：
2012
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Yuri Faenza;G. Oriolo;Gautier Stauffer
通讯作者：
Gautier Stauffer
完全未成年人的极值函数
DOI：
10.1006/jctb.2000.2013
发表时间：
2001
期刊：
J. Comb. Theory B
影响因子：
--
作者：
A. Thomason
通讯作者：
A. Thomason