Campus Event Calendar
Event Entry
New for: D1
What and Who
Probabilistic Analyses of PPZ
Yanheng Wang
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 29 August 2023
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
The PPZ algorithm [Paturi-Pudlák-Zane 1997] for k-SAT proceeds by assigning 0/1 values to variables in a random order. Each value is sampled uniformly at random, unless we can read it off from the partially evaluated formula. One may lower bound the success probability by 2^{-n + n/k} where n is the number of variables. On the other hand, the bound is tight on particular (somewhat stringent) instances.
In this talk, I will present a graphical model that captures the complexity of PPZ on a broad class of instances. Focusing on upper bounds, I will present three probabilistic approaches, drawing ideas from statistical physics and information theory. The last approach yields a tight upper bound of 2^{-n + cn \log k/k} on these instances, for some constant c>0. This is joint work with my thesis advisor Dominik Scheder.
Contact
Roohani Sharma
+49 681 9325 1116
--email hidden
Virtual Meeting Details
Zoom
527 278 8807
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
If you wish to attend the talk but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.
Roohani Sharma, 08/29/2023 09:23 -- Created document.