English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

There has been a lot of interest recently in proving lower bounds on the sizeof linear programs needed to represent a given polytope P. In a breakthroughpaper Fiorini et al. [Proceedings of 44th ACM Symposium on Theory of Computing2012, pages 95-106] showed that any linear programming formulation ofmaximum-cut must have exponential size. A natural question to ask is whetherone can prove such strong lower bounds for semidefinite programmingformulations. In this paper we take a step towards this goal and we provestrong lower bounds for a certain class of SDP formulations, namely SDPs overthe Cartesian product of fixed-size positive semidefinite cones. In practicethis corresponds to semidefinite programs with a block-diagonal structure andwhere blocks have constant size d. We show that any such extended formulationof the cut polytope must have exponential size (when d is fixed). The result ofFiorini et al. for LP formulations is obtained as a special case when d=1. Forblocks of size d=2 the result rules out any small formulations usingsecond-order cone programming. Our study of SDP lifts over Cartesian product offixed-size positive semidefinite cones is motivated mainly from practicalconsiderations where it is well known that such SDPs can be solved moreefficiently than general SDPs. The proof of our lower bound relies on newresults about the sparsity pattern of certain matrices with small psd rank,combined with an induction argument inspired from the recent paper by Kaibeland Weltge [arXiv:1307.3543] on the LP extension complexity of the correlationpolytope.

Exponential lower bounds on fixed-size psd rank and semidefinite extension complexity