David Witmer

activity

20122017

most citedSum of squares lower bounds for refuting any CSP

11 citations · 39 across the 5 of their papers we have counts for

collaborators

7 papers

cs.CC2017★ 11 cited

Sum of squares lower bounds for refuting any CSP

Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell +1

Let $P : {0, 1}^{k} \to {0, 1}$ be a nontrivial $k$ -ary predicate. Consider a random instance of the constraint satisfaction problem $CSP (P)$ on $n$ variables with $Δ n$ cons…

cs.CC2016★ 3 cited

Lower bounds for CSP refutation by SDP hierarchies

Ryuhei Mori, David Witmer

For a $k$ -ary predicate $P$ , a random instance of CSP $(P)$ with $n$ variables and $m$ constraints is unsatisfiable with high probability when $m ≫ n$ . The natural algorithmic tas…

cs.IT2015★ 9 cited

Remarks on the Most Informative Function Conjecture at fixed mean

Guy Kindler, Ryan O'Donnell, David Witmer

In 2013, Courtade and Kumar posed the following problem: Let $x \sim {\pm 1}^{n}$ be uniformly random, and form $y \sim {\pm 1}^{n}$ by negating each bit…

cs.CC2015★ 8 cited

How to refute a random CSP

Sarah R. Allen, Ryan O'Donnell, David Witmer

Let $P$ be a $k$ -ary predicate over a finite alphabet. Consider a random CSP $(P)$ instance $I$ over $n$ variables with $m$ constraints. When $m ≫ n$ the instance $I$ will be unsa…

cs.CC2015★ 8 cited

Beating the random assignment on constraint satisfaction problems of bounded degree

Boaz Barak, Ankur Moitra, Ryan O'Donnell +7

We show that for any odd $k$ and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac…

cs.DS2013

Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results

Anupam Gupta, Kunal Talwar, David Witmer

We give a 2-approximation algorithm for Non-Uniform Sparsest Cut that runs in time $n^{O (k)}$ , where $k$ is the treewidth of the graph. This improves on the previous $2^{2^{k}}$ -appr…