Extended formulations, non-negative factorizations and randomized communication protocols

Details Extended formulations, non-negative factorizations and randomized communication protocols Extended formulations, non-negative factorizations and randomized communication protocols

2011-05-20

arxiv.org/abs/1105.4127v2

Computer Science

Discrete Mathematics

16 pages, 3 figures

Scientific paper

We show that the binary logarithm of the non-negative rank of a non-negative
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.

Affiliated with

Also associated with

No associations

Rating

Extended formulations, non-negative factorizations and randomized communication protocols does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Extended formulations, non-negative factorizations and randomized communication protocols, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extended formulations, non-negative factorizations and randomized communication protocols will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-650269