Local enumeration: the not-all-equal case

DOI10.4230/LIPICS.STACS.2025.42MaRDI QIDQ7287779zbMATH OpenFDO

Authors Mohit Gurumukhani, Ramamohan Paturi, Michael Saks, Navid Talebanfard

Publication date 24 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2025.42

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A probabilistic algorithm for k-SAT based on limited local search and restart
• An improved exponential-time algorithm for k -SAT
• Breaking the PPSZ barrier for unique 3-SAT
• Depth-three circuits for inner product and majority functions
• Faster k-SAT algorithms using biased-PPSZ
• scientific article; zbMATH DE number 1452705 (Why is no real title available?)
• scientific article; zbMATH DE number 7829304 (Why is no real title available?)
• Local enumeration and majority lower bounds
• On super strong ETH
• PPSZ is better than you think
• Solving satisfiability in less than \(2^ n\) steps
• Super strong ETH is true for PPSZ with small resolution width
• The composition complexity of majority
• Top-down lower bounds for depth-three circuits

This page was built for publication: Local enumeration: the not-all-equal case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7287779)