Extended formulations, nonnegative factorizations, and randomized communication protocols

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10318087" target="_blank" >RIV/00216208:11320/15:10318087 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s10107-014-0755-3" target="_blank" >http://dx.doi.org/10.1007/s10107-014-0755-3</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10107-014-0755-3" target="_blank" >10.1007/s10107-014-0755-3</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Extended formulations, nonnegative factorizations, and randomized communication protocols

Popis výsledku v původním jazyce

An extended formulation of a polyhedron is a linear description of a polyhedron together with a linear map such 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 of equals thenonnegative rank of its slack matrix . Moreover, Yannakakis also shows that the nonnegative rank of is at most , where is the complexity of any deterministic protocol computing . In this paper, we show that the latter result can be strengthened when weallow protocols to be randomized. 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.

Název v anglickém jazyce

Extended formulations, nonnegative factorizations, and randomized communication protocols

Popis výsledku anglicky

An extended formulation of a polyhedron is a linear description of a polyhedron together with a linear map such 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 of equals thenonnegative rank of its slack matrix . Moreover, Yannakakis also shows that the nonnegative rank of is at most , where is the complexity of any deterministic protocol computing . In this paper, we show that the latter result can be strengthened when weallow protocols to be randomized. 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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Mathematical Programming, Series B

ISSN

0025-5610

e-ISSN

—

Svazek periodika

153

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

20

Strana od-do

75-94

Kód UT WoS článku

000361473100006

EID výsledku v databázi Scopus

2-s2.0-84941997801