Independent Set Polytopes: Query vs. Communication Perspective
summary
Constructs n‑node graphs whose independent set polytope provably requires extension complexity nearly maximal namely exp(n / log n), via a reduction from a hard query search problem (Tseitin XOR on expanders) composed with a small communication gadget and encoded by cliques that map constraint assignments to independent sets. Also shows a tight fixed‑parameter regime: if the independence number is k the extension complexity matches the trivial bound up to constants at n^k. The proof uses conical junta degree, lifting theorems and nonnegative rank arguments.
AI-written summary · about