Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-179 | 31st October 2018 08:59

PPSZ on CSP Instances with Multiple Solutions

RSS-Feed




TR18-179
Authors: Dominik Scheder
Publication: 31st October 2018 22:38
Downloads: 745
Keywords: 


Abstract:

We study the success probability of the PPSZ algorithm on $(d,k)$-CSP formulas. We greatly simplify the analysis of Hertli, Hurbain, Millius, Moser, Szedlak, and myself for the notoriously difficult case that the input formula has more than one satisfying assignment.



ISSN 1433-8092 | Imprint