Fetching the paper…

Reading the bibliography…

2014

Some upper and lower bounds on PSD-rank

Lee, Troy, Wei, Zhaohui, de Wolf, Ronald

Original
PDF
Post on X

Understand

Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity.

We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank.
All of these bounds are based on viewing a positive semidefinite factorization of a matrix $M$ as a quantum communication protocol.
These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques.

Some upper and lower bounds on PSD-rank · Around

Built on

Expressing combinatorial optimization problems by linear programs
M. Yannakakis · 1991
Earlier work this paper cites.
Quantum Computation and Quantum Information
M. Nielsen and I. Chuang · 2000
Earlier work this paper cites.
On polyhedral approximations of the second-order cone
A. Ben-Tal and A. Nemirovski · 2001
Earlier work this paper cites.
Perturbed identity matrices have high rank: proof and applications
N. Alon · 2009
Earlier work this paper cites.
Extended formulations, non-negative factorizations and randomized communication protocols
Original
M. Conforti, Y. Faenza, S. Fiorini, and H. R. Tiwary · 2012
Earlier work this paper cites.

Similar

Linear vs. semidefinite extended formulations: Exponential separation and strong lower bounds
S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. de Wolf · 2012
Cited alongside, same era.
New lower bounds on nonnegative rank using conic programming
Original
H. Fawzi and P. Parrilo · 2012
Cited alongside, same era.
Support based bounds for positive semidefinite rank
Original
T. Lee and D. O. Theis · 2012
Cited alongside, same era.
Quantum strategic game theory
Original
S. Zhang · 2012
Cited alongside, same era.
personal communication
G. Braun and S. Pokutta
Cited in the paper.

Then

Lifts of convex sets and cone factorizations
Original
J. Gouveia, P. Parrilo, and R. Thomas · 2013
Later among the works it cites.
Efficient protocols for generating bipartite classical distributions and quantum states
R. Jain, Y. Shi, Z. Wei, and S. Zhang · 2013
Later among the works it cites.
Positive semidefinite rank
Original
H. Fawzi, J. Gouveia, P. Parrilo, R. Robinson, and R. Thomas · 2014
Closest in time.
The matching polytope has exponential extension complexity
T. Rothvoß · 2014
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…