Common Information and Unique Disjointness
Common Information and Unique Disjointness
复制标题
共同信息和独特的脱节
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
S. Pokutta
中科院分区：
文献类型：
--
作者：
Gábor Braun;S. Pokutta
我们提供了一个信息论框架，用于通过公共信息建立矩阵非负秩的强下界，这是 Wyner 先前引入的概念（IEEE Trans Inf Theory 21(2):163–179, 1975）。该框架是 Braverman 和 Moitra（第 45 届 ACM 计算理论年度研讨会论文集，第 161-170 页，2013 年）中针对移位唯一不相交 (UDISJ) 矩阵到任意非负矩阵的框架的推广。公共信息是矩阵非负秩的自然下界，通过将其与 Hellinger 距离估计相结合，我们计算出 UDISJ 部分矩阵的（几乎）精确的公共信息。边界是非常自然地获得的。我们还在随机或对抗性删除 UDISJ 部分矩阵的行和列的情况下建立了该估计的稳健性。这种鲁棒性通过 Yannakakis 因式分解定理的变体转化为平均情况和移除的对抗性近似扩展复杂度的下界。我们提出了第一个多胞体家族，即布劳恩等人引入的硬对。 (Math Oper Res 40(3):756–772, 2015) 与 CLIQUE 问题相关，具有较高的平均情况和移除的对抗性近似扩展复杂性。该框架依赖于 Bar-Yossef 的信息论和 Hellinger 距离之间联系的强化版本（J Comput Syst Sci 68(4):702–732, 2004）。我们还提供了愚弄集方法的信息论变体，它允许我们将愚弄集下界从扩展复杂性扩展到近似扩展复杂性。
We provide an information-theoretic framework for establishing strong lower bounds on the nonnegative rank of matrices by means of common information, a notion previously introduced in Wyner (IEEE Trans Inf Theory 21(2):163–179, 1975). The framework is a generalization of the one in Braverman and Moitra (Proceedings of the forty-fifth annual ACM symposium on theory of computing, pp 161–170, 2013) for the shifted uniqe disjointness (UDISJ) matrix to arbitrary nonnegative matrices. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with Hellinger distance estimations we compute the (almost) exact common information of UDISJ partial matrix. The bounds are obtained very naturally. We also establish robustness of this estimation under random or adversarial removal of rows and columns of the UDISJ partial matrix. This robustness translates, via a variant of Yannakakis’s factorization theorem, to lower bounds on the average case and adversarial approximate extension complexity of removals. We present the first family of polytopes, the hard pair introduced in Braun et al. (Math Oper Res 40(3):756–772, 2015) related to the CLIQUE problem, with high average case and adversarial approximate extension complexity of removals. The framework relies on a strengthened version of the link between information theory and Hellinger distance from Bar-Yossef (J Comput Syst Sci 68(4):702–732, 2004). We also provide an information theoretic variant of the fooling set method that allows us to extend fooling set lower bounds from extension complexity to approximate extension complexity.
扩展公式、非负分解和随机通信协议
影响因子：
2.7
作者：
Y. Faenza;S. Fiorini;R. Grappe;H.R. Tiwary
通讯作者：
H.R. Tiwary