[Colloquium] Departments of Computer Science & Mathematics Combinatorics & Theoretical Seminar

[Donna Brooms]

*REMINDER*

COMBINATORICS & THEORETICAL COMPUTER SCIENCE SEMINAR

Tuesday, April 19, 2016
3:00 pm
Ryerson 251

Daivd Witmer
Carnegie Mellon University
www.cs.cmu.edu/~dwitmer/

Consider a random constraint satisfaction problem (CSP) over $n$ variables with $m$ constraints, each being a predicate $P$ applied to $k$ random literals. When $m \gg n$ the instance will be unsatisfiable with high probability, and the natural associated algorithmic task is to find a refutation --- i.e., a certificate of unsatisfiability.

Understanding the density required for average-case refutation is important in various areas of complexity including cryptography, proof complexity, and learning theory.

 

In this talk, we give a general criterion that often allows efficient refutation at much lower densities than previous algorithms. Specifically, if $P$ fails to support a $t$-wise uniform probability distribution, then there is an efficient algorithm that refutes random instances with high probability, provided $m \gg n^{t/2}$.  Indeed, our algorithm will ``somewhat strongly'' refute instances, certifying that the optimum is bounded away from 1.  If $t = k$, then we furthermore get the strongest possible refutation, certifying that the optimum is within o(1) of its expectation.  This last result is new even in the context of random $k$-SAT.  Our refutation algorithm can be carried out by the $O(1)$-round SOS SDP hierarchy and prior work on SDP hierarchies provides evidence that its dependence on $m$ is optimal for every $P$.

This is joint work with Sarah R. Allen and Ryan O’Donnell.

 Refreshments will be served prior to the talk in Ryerson 255 at 3pm
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160419/1a277ec9/attachment.htm