BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

David Witmer

David Witmer contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsComputational ComplexityInformation Theorymath.IT

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

5 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access