Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication
A classical result from Yannakakis states that $$\text{xc}(P) = \text{rank}_+(S),$$ where \(P\) is a polytope with slack matrix \(S\). Yannakakis further showed that with nondeterministic communication complexity, one can give a lower bound for the nonnegative rank.
This lower bound is sufficient to prove that some polytopes, like the correlation polytope, have exponential extension complexity. However, it fails for many other examples.
In a 2013 paper, "Extended formulations, nonnegative factorizations, and randomized
communication protocols," by Faenza, Fiorini, Grappe, and Tiwary, they show that a model of randomized communication complexity can not only lower bound nonnegative rank, but exactly characterize it.
In my communication complexity reading group, I gave a talk presenting this paper and its results. The proofs are extremely elegant and simple, making for a very enjoyable read.
For those interested, here is a link to my lecture notes!
cool, love to see more!
ReplyDeleteIn much less colorful language, avoid half in} slot machines with terrible odds of profitable. Chen stated previous research has proven that some 70 % of casino revenues come from slot machines, up drastically from the 1970s when that determine was closer to 40 %. Not surprisingly, a 2006 survey showed that 71 % of casino gamblers favor slot machines and/or video poker over other video games. Seminole Hard Rock Tampa certainly one of the|is among the|is doubtless one of the} largest casinos in the United States with an array of slot machines that will thrill your senses. Our casino offers a variety 온라인 카지노 순위 of|quite so much of|a big selection of} slots together with a number of the} most popular machines.
ReplyDelete