Skip to main content
To KTH's start page To KTH's start page

Jonah Brown-Cohen: Extended Formulation Lower Bounds for Refuting Random CSPs

Time: Mon 2019-04-29 12.00

Location: Room 4523, Lindstedtsvägen 5 - floor 5, KTH

Participating: Jonah Brown-Cohen

Export to calendar

Lunch is served at 12:00 noon (register at  at the latest the
Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.

There will be a more detailed technical discussionafter the seminar.


Random constraint satisfaction problems (CSPs) such as random 3-SAT are conjectured to be computationally intractable. The average case hardness of random 3-SAT and other CSPs has broad and far-reaching implications for problems in approximation, learning theory and cryptography. In many cases, the best known algorithms for CSPs come from linear or semi-definite programs, so a natural question is to prove lower bounds on the size of such programs for random CSPs.

In this talk, we will give sub-exponential lower bounds on the size of linear programming extended formulations for refuting random instances of constraint satisfaction problems. In particular, our results imply that any LP extended formulation that refutes a constant fraction of random k-SAT instances (with constant clause density) must have size exponential in \(n^{1- 2/k}\).

We use the technique of pseudo-calibration to directly obtain extended formulation lower bounds from the distribution on instances with a planted satisfying assignment. This approach bypasses the need to construct Sherali-Adams integrality gaps in proving general LP extended formulation lower bounds. As a corollary, we obtain a self-contained proof of sub-exponential Sherali-Adams LP lower bounds for these problems.

For more information about upcoming seminars,