Search Mailing List Archives
[theory-seminar] Theory Seminar (Thursday 5/23): Andrea Lincoln
Ofir Geri
ofirgeri at stanford.edu
Mon May 20 13:34:22 PDT 2019
Hi all,
This week, Andrea Lincoln (MIT) will give a theory seminar talk on Faster Random k-CNF Satisfiability (see abstract below).
The talk will be on THURSDAY at 4:15 PM in Gates 463A. Please note the non-standard day and time.
The abstracts of past and upcoming seminar talks are also available on the theory seminar webpage:
http://theory.stanford.edu/seminar/
Hope to see you there!
Ofir
Faster Random k-CNF Satisfiability
Speaker: Andrea Lincoln (MIT)
We describe an algorithm to solve the problem of Boolean CNF-Satisfiability when the input formula is chosen randomly.
We build upon the algorithms of Schöning 1999 and Dantsin et al. in 2002. The Schöning algorithm works by trying many possible random assignments, and for each one searching systematically in the neighborhood of that assignment for a satisfying solution. Previous algorithms for this problem run in time O(2^{n (1- \Omega(1)/k)}).
Our improvement is simple: we count how many clauses are satisfied by each randomly sampled assignment, and only search in the neighborhoods of assignments with abnormally many satisfied clauses. We show that assignments like these are significantly more likely to be near a satisfying assignment. This improvement saves a factor of 2^{n \Omega(\lg^2 k)/k}, resulting in an overall runtime of O(2^{n (1- \Omega(\lg^2 k)/k)}) for random k-SAT.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20190520/ab79c0ba/attachment-0001.html>
More information about the theory-seminar
mailing list