All reports by Author Joshua Brakensiek:

__
TR20-004
| 17th January 2020
__

Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny#### The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs

__
TR19-054
| 9th April 2019
__

Joshua Brakensiek, Venkatesan Guruswami#### Bridging between 0/1 and Linear Programming via Random Walks

Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny

In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not ... more >>>

Joshua Brakensiek, Venkatesan Guruswami

Under the Strong Exponential Time Hypothesis, an integer linear program with $n$ Boolean-valued variables and $m$ equations cannot be solved in $c^n$ time for any constant $c < 2$. If the domain of the variables is relaxed to $[0,1]$, the associated linear program can of course be solved in polynomial ... more >>>