Exponential bounds for DPLL below the satisfiability threshold

No abstract is available for this paper.

• Publication year

  2004

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2004-01-11

• Fields of study

  Mathematics, Computer Science

• Identifiers

  No identifiers available.

• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A sharp threshold in proof complexity

  2001cited by this paper
• Lower bounds for random 3-SAT via differential equations

  2001cited by this paper
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problem

  1990cited by this paper
• Many hard examples for resolution

  1988cited by this paper

• Asymptotically Optimal Inapproximability of Ek-SAT Reconfiguration

  2025cites this paper
• Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems

  2023cites this paper
• Quantum hybrid algorithm for solving SAT problem

  2023cites this paper
• The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials

  2021cites this paper
• Opleiding Informatica Hybrid Classical-Quantum Speedups for the Random k -SAT Problem using Smaller Quantum Computers

  2020cites this paper
• Improved Bounds for Noisy Group Testing With Constant Tests per Item

  2020cites this paper
• 24 : 2 Dismantlability , connectedness , and mixing in relational structures

  2019cites this paper
• Dismantlability, Connectedness, and Mixing in Relational Structures

  2019cites this paper
• Why does Lookahead work ?

  2017influential citation
• Belief Propagation Guided Decimation Fails on Random Formulas

  2017cites this paper
• Analysing Survey Propagation Guided Decimation on Random Formulas

  2016cites this paper
• Walksat Stalls Well Below Satisfiability

  2016influential citation
• Quantum Speed-ups for Boolean Satisfiability and Derivative-Free Optimization

  2014cites this paper
• Resolution and Parallelizability: Barriers to the Efficient Parallelization of SAT Solvers

  2013cites this paper
• Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic

  2011cites this paper
• On belief propagation guided decimation for random k-SAT

  2010cites this paper
• Structure-based satisfiability checking

  2009cites this paper
• A Better Algorithm for Random k-SAT

  2009cites this paper
• Analyzing and Harnessing the Potential

  2008cites this paper
• A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems

  2008cites this paper
• Chapter 8 Random Satisfiability

  2008cites this paper
• Threshold Phenomena in Random Constraint Satisfaction Problems

  2008cites this paper
• Se p 20 06 The Connectivity of Boolean Satisfiability : Computational and Structural Dichotomies

  2008cites this paper
• IMPACT OF RESTRICTED BRANCHING ON CLAUSE LEARNING SAT SOLVING

  2007cites this paper
• Limitations of restricted branching in clause learning

  2007cites this paper
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

  2006cites this paper
• Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas

  2004cites this paper
• Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold

  2003cites this paper
• Many hard examples in exact phase transitions

  2003cites this paper