Publication

Extended Formulations, Nonnegative Factorizations, and Randomized Communication Protocols

Yuri Faenza, Hans Raj Tiwary
2012
Conference Papers

Abstract

We show that the binary logarithm of the nonnegative rank of a nonnegative matrix is, up to small constants, equal to the minimum complexity of a randomized communication protocol computing the matrix in expectation. We use this connection to prove new conditional lower bounds on the sizes of extended formulations, in particular, for perfect matching polytopes.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Extended Formulations, Nonnegative Factorizations, and Randomized Communication Protocols

Chat with Graph Search

On the Use of the Generalized Littlewood Theorem Concerning Integrals of the Logarithm of Analytical Functions for the Calculation of Infinite Sums and the Analysis of Zeroes of Analytical Functions

Chung-type law of the iterated logarithm and exact moduli of continuity for a class of anisotropic Gaussian random fields

Propagation of singularities for the stochastic wave equation