On the extension complexity of polytopes separating subsets of the Boolean cube

Authors

Abstract: We show that 1. for every

A s u b s e t e q {0, 1}^{n}

, there exists a polytope

P s u b s e t e q m a t h b b R^{n}

with

P c a p {0, 1}^{n} = A

and extension complexity

O (2^{n / 2})

, 2. there exists an

A s u b s e t e q {0, 1}^{n}

such that the extension complexity of any

P

with

P c a p {0, 1}^{n} = A

must be at least

2^{f r a c n 3 (1 - o (1))}

. We also remark that the extension complexity of any 0/1-polytope in

m a t h b b R^{n}

is at most

O (2^{n} / n)

and pose the problem whether the upper bound can be improved to

O (2^{c n})

, for

c < 1

.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: On the extension complexity of polytopes separating subsets of the Boolean cube