Source author record

David Witmer

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms Information Theory math.IT

Catalog footprint

Research overview

6works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Lower bounds for CSP refutation by SDP hierarchies

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 \gg n$ . The natural algorithmic task in this regime is \emph{refutation}: finding a proof that a given random instance is unsatisfiable. Recent work of Allen et al. suggests that the difficulty of refuting CSP $(P)$ using an SDP is determined by a parameter $\mathrm{cmplx}(P)$ , the smallest $t$ for which there does not exist a $t$ -wise uniform distribution over satisfying assignments to $P$ . In particular they show that random instances of CSP $(P)$ with $m \gg n^{\mathrm{cmplx(P)}/2}$ can be refuted efficiently using an SDP. In this work, we give evidence that $n^{\mathrm{cmplx}(P)/2}$ constraints are also \emph{necessary} for refutation using SDPs. Specifically, we show that if $P$ supports a $(t-1)$ -wise uniform distribution over satisfying assignments, then the Sherali-Adams $_+$ and Lovász-Schrijver $_+$ SDP hierarchies cannot refute a random instance of CSP $(P)$ in polynomial time for any $m \leq n^{t/2-ε}$ .

preprint2016arXiv

Remarks on the Most Informative Function Conjecture at fixed mean

In 2013, Courtade and Kumar posed the following problem: Let $\boldsymbol{x} \sim \{\pm 1\}^n$ be uniformly random, and form $\boldsymbol{y} \sim \{\pm 1\}^n$ by negating each bit of $\boldsymbol{x}$ independently with probability $α$ . Is it true that the mutual information $I(f(\boldsymbol{x}) \mathbin{;} \boldsymbol{y})$ is maximized among $f:\{\pm 1\}^n \to \{\pm 1\}$ by $f(x) = x_1$ ? We do not resolve this problem. Instead, we make a couple of observations about the fixed-mean version of the conjecture. We show that Courtade and Kumar's stronger Lex Conjecture fails for small noise rates. We also prove a continuous version of the conjecture on the sphere and show that it implies the previously-known analogue for Gaussian space.

preprint2015arXiv

Beating the random assignment on constraint satisfaction problems of bounded degree

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{1}{2} + Ω(1/\sqrt{D})$ fraction of constraints, where $D$ is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a \emph{quantum} algorithm to find an assignment satisfying a $\frac{1}{2} + Ω(D^{-3/4})$ fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a $μ+ Ω(1/\sqrt{D})$ fraction of constraints, where $μ$ is the fraction that would be satisfied by a uniformly random assignment.

preprint2015arXiv

How to refute a random CSP

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 \gg n$ the instance $I$ will be unsatisfiable with high probability, and we want to find a refutation - i.e., a certificate of unsatisfiability. When $P$ is the $3$ -ary OR predicate, this is the well studied problem of refuting random $3$ -SAT formulas, and an efficient algorithm is known only when $m \gg n^{3/2}$ . Understanding the density required for refutation of other predicates is important in cryptography, proof complexity, and learning theory. Previously, it was known that for a $k$ -ary predicate, having $m \gg n^{\lceil k/2 \rceil}$ constraints suffices for refutation. We give a criterion for predicates that often yields efficient refutation algorithms at much lower densities. Specifically, if $P$ fails to support a $t$ -wise uniform distribution, then there is an efficient algorithm that refutes random CSP $(P)$ instances $I$ whp when $m \gg n^{t/2}$ . Indeed, our algorithm will "somewhat strongly" refute $I$ , certifying $\mathrm{Opt}(I) \leq 1-Ω_k(1)$ , if $t = k$ then we get the strongest possible refutation, certifying $\mathrm{Opt}(I) \leq \mathrm{E}[P] + o(1)$ . This last result is new even in the context of random $k$ -SAT. Regarding the optimality of our $m \gg n^{t/2}$ requirement, prior work on SDP hierarchies has given some evidence that efficient refutation of random CSP $(P)$ may be impossible when $m \ll n^{t/2}$ . Thus there is an indication our algorithm's dependence on $m$ is optimal for every $P$ , at least in the context of SDP hierarchies. Along these lines, we show that our refutation algorithm can be carried out by the $O(1)$ -round SOS SDP hierarchy. Finally, as an application of our result, we falsify assumptions used to show hardness-of-learning results in recent work of Daniely, Linial, and Shalev-Shwartz.

preprint2013arXiv

Markov chain methods for small-set expansion

Consider a finite irreducible Markov chain with invariant distribution $π$ . We use the inner product induced by $π$ and the associated heat operator to simplify and generalize some results related to graph partitioning and the small-set expansion problem. For example, Steurer showed a tight connection between the number of small eigenvalues of a graph's Laplacian and the expansion of small sets in that graph. We give a simplified proof which generalizes to the nonregular, directed case. This result implies an approximation algorithm for an "analytic" version of the Small-Set Expansion Problem, which, in turn, immediately gives an approximation algorithm for Small-Set Expansion. We also give a simpler proof of a lower bound on the probability that a random walk stays within a set; this result was used in some recent works on finding small sparse cuts.

preprint2013arXiv

Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results

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}$ -approximation in time $\poly(n) 2^{O(k)}$ due to Chlamtáč et al. To complement this algorithm, we show the following hardness results: If the Non-Uniform Sparsest Cut problem has a $ρ$ -approximation for series-parallel graphs (where $ρ\geq 1$ ), then the Max Cut problem has an algorithm with approximation factor arbitrarily close to $1/ρ$ . Hence, even for such restricted graphs (which have treewidth 2), the Sparsest Cut problem is NP-hard to approximate better than $17/16 - ε$ for $ε> 0$ ; assuming the Unique Games Conjecture the hardness becomes $1/α_{GW} - ε$ . For graphs with large (but constant) treewidth, we show a hardness result of $2 - ε$ assuming the Unique Games Conjecture. Our algorithm rounds a linear program based on (a subset of) the Sherali-Adams lift of the standard Sparsest Cut LP. We show that even for treewidth-2 graphs, the LP has an integrality gap close to 2 even after polynomially many rounds of Sherali-Adams. Hence our approach cannot be improved even on such restricted graphs without using a stronger relaxation.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.