A full derandomization of schöning's k-SAT algorithm

DOI10.1145/1993636.1993670zbMath1288.68245arXiv1008.4067OpenAlexW2168704151MaRDI QIDQ5419094

Robin A. Moser, Dominik Scheder

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1008.4067

zbMATH Keywords

deterministicderandomizationSchöning's algorithm\(k\)-\textsc{SAT}\textsc{SAT}

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05)

Related Items (19)

Strong partial clones and the time complexity of SAT problems ⋮ A satisfiability algorithm and average-case hardness for formulas over the full binary basis ⋮ Unnamed Item ⋮ Derandomizing the HSSW algorithm for 3-SAT ⋮ Using small-scale quantum devices to solve algebraic equations ⋮ A combinatorial analysis for the critical clause tree ⋮ A new upper bound for \(( n , 3)\)-MAX-SAT ⋮ An exact exponential time algorithm for counting bipartite cliques ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps ⋮ Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT ⋮ Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT ⋮ Satisfiability Certificates Verifiable in Subexponential Time ⋮ An initial study of time complexity in infinite-domain constraint satisfaction ⋮ Unnamed Item ⋮ The string guessing problem as a method to prove lower bounds on the advice complexity ⋮ A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles ⋮ Basic Terminology, Notation and Results ⋮ Unnamed Item

This page was built for publication: A full derandomization of schöning's k-SAT algorithm