Search Mailing List Archives
[theory-seminar] Theory Lunch 5/16 -- Joshua Brakensiek
Weiyun Ma
wyma at stanford.edu
Mon May 13 14:42:07 PDT 2019
Hi all,
This Thursday at theory lunch, Josh will tell us about "Bridging between 0/1 and Linear Programming via Random Walks." (See abstract below.)
As usual, please join us from noon to 1pm at 463A.
----------------------------------------------------------
Bridging between 0/1 and Linear Programming via Random Walks
Speaker: Joshua Brakensiek
Under the Strong Exponential Time Hypothesis, an integer linear program with n Boolean-valued variables and m equations cannot be solved in c^n time for any constant c < 2. If the domain of the variables is relaxed to [0,1], the associated linear program can of course be solved in polynomial time. In this work, we give a natural algorithmic bridging between these extremes of 0-1 and linear programming. Specifically, for any subset (finite union of intervals) E \subset [0,1] containing {0, 1}, we give a random-walk based algorithm with runtime ~(2-measure(E))^n (up to polynomial factors) that finds a solution in E^n to any n-variable linear program with m constraints that is feasible over {0,1}^n. Note that as E expands from {0,1} to [0,1], the runtime improves smoothly from 2^n to polynomial.
Taking E = [0,1/k) \cup (1-1/k,1] in our result yields as a corollary a randomized ~(2-2/k)^n time algorithm for
k-SAT, recovering a result of Schoning (FOCS 1999). While our approach has some high level resemblance to Schoning's beautiful algorithm, our general algorithm is based on a more sophisticated random walk that incorporates several new ingredients, such as a multiplicative potential to measure progress, a judicious choice of starting distribution, and a time varying distribution for the evolution of the random walk that is itself computed via an LP at each step (a solution to which is guaranteed based on the minimax theorem).
Joint work with Venkatesan Guruswami (CMU).
----------------------------------------------------------
Best,
Anna
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20190513/77be75b5/attachment-0001.html>
More information about the theory-seminar
mailing list