Some upper and lower bounds on PSD-rank

Troy Lee, Zhaohui Wei, Ronald de Wolf

Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity. We first study several basic proper…