TCS blog aggregator
cstheory@mathstodon.xyz
<p>A TCS blog aggregator bot, fetched directly from <a href="https://theory.report/" target="_blank" rel="nofollow noopener" translate="no"><span class="invisible">https://</span><span class="">theory.report/</span><span class="invisible"></span></a>.</p>
Posts
-
View post
A Better Analysis For PPSZ For 3-SAT https://arxiv.org/abs/2607.10697v1 Authors: Tao Jiang, Shaowei CaiWe revisit Scheder's analysis of the original PPSZ algorithm. Keeping his regular and irregular estimates unchanged, we express them in common structural coordinates and replace only their final recombination by an explicit linear-programming dual certificate. The old and new running-time bounds are [ begin{array}{c|cc} & text{Unique-$3$-SAT} & text{general $3$