The encoding conjecture for convex-formulation languages

About 15 years old · traced to

Let CF\mathbf{CF} be the class of languages L⊆{0,1}∗L\subseteq\{0,1\}^* whose length-nn slices have convex hulls admitting extended formulations of polynomial size, and let CFenc⁡\mathbf{CF}^{\operatorname{enc}} be the subclass admitting such formulations with integral coefficients of polynomial encoding length.

Encoding conjecture.

CFenc⁡=CF.\mathbf{CF}^{\operatorname{enc}}=\mathbf{CF}.

The inclusion CFenc⁡⊆CF\mathbf{CF}^{\operatorname{enc}}\subseteq\mathbf{CF} is immediate, while the reverse inclusion would say that every polynomial-size extended formulation can be replaced by one with polynomially bounded encoding length. The source presents this as an open conjecture; its significance is that it would identify the unrestricted and efficiently encodable classes of languages described by polynomial-size extended formulations.

References

Primary source

Thomas Rothvoß, “Some 0/1 polytopes need exponential size extended formulations”, arXiv:1105.0036 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.