38 citations · 38 across the 1 of their papers we have counts for
3 papers
cs.CC2013
Breaking the PPSZ Barrier for Unique 3-SAT
Timon Hertli
The PPSZ algorithm by Paturi, Pudlák, Saks, and Zane (FOCS 1998) is the fastest known algorithm for (Promise) Unique k-SAT. We give an improved algorithm with exponentially faster…
cs.CC2011★ 38 cited
3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
Timon Hertli
The PPSZ algorithm by Paturi, Pudlák, Saks, and Zane [1998] is the fastest known algorithm for Unique k-SAT, where the input formula does not have more than one satisfying assignme…
cs.DS2010
Improving PPSZ for 3-SAT using Critical Variables
Timon Hertli, Robin A. Moser, Dominik Scheder
A critical variable of a satisfiable CNF formula is a variable that has the same value in all satisfying assignments. Using a simple case distinction on the fraction of critical va…