The resolution complexity of random constraint satisfaction problems

No abstract is available for this paper.

• Publication year

  2003

• Venue

  44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.

• Publication date

  2003-10-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/SFCS.2003.1238207
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The resolution complexity of random graph k-colorability

  2005cited by this paper
• Coarse and Sharp Transitions for Random Generalized Satisfyability Problems

  2004cited by this paper
• Models for Random Constraint Satisfaction Problems

  2003cited by this paper
• A probabilistic analysis of randomly generated binary constraint satisfaction problems

  2003cited by this paper
• Resolution complexity of random constraint satisfaction problems: Another half of the story

  2003cited by this paper
• Resolution Complexity of Random Constraints

  2002cited by this paper
• Random generalized satisfiability problems

  2002cited by this paper
• The resolution complexity of constraint satisfaction

  2002cited by this paper
• The Efficiency of Resolution and Davis--Putnam Procedures

  2002cited by this paper
• Random 2-SAT: results and problems

  2001cited by this paper
• A sharp threshold in proof complexity

  2001cited by this paper
• Approximating the Satisfiability Threshold for Random k-XOR-formulas

  2001cited by this paper
• Short proofs are narrow—resolution made simple

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

  2001cited by this paper
• Random Constraint Satisfaction: Flaws and Structure

  2001cited by this paper
• Rigorous results for random (2+p)-SAT

  2001cited by this paper
• Random graphs

  2000cited by this paper
• Exact Phase Transitions in Random Constraint Satisfaction Problems

  2000cited by this paper
• Satisfiability Threshold for Random XOR-CNF Formulas

  1999cited by this paper
• 2+p‐SAT: Relation of typical‐case complexity to the nature of the phase transition

  1999cited by this paper
• Approximating the unsatisfiability threshold of random formulas

  1998cited by this paper
• Tricritical points in random combinatorics: the -SAT case

  1998cited by this paper
• Random Constraint Satisfaction: A More Accurate Picture

  1997influential reference
• Simplified and improved resolution lower bounds

  1996cited by this paper
• Phase transition and search cost in the 2+p-sat problem

  1996cited by this paper
• Approximating the Unsatissability Threshold of Random Formulas

  1995cited by this paper
• A Threshold for Unsatisfiability

  1992cited by this paper
• Mick gets some (the odds are on his side) (satisfiability)

  1992cited by this paper
• Many hard examples for resolution

  1988cited by this paper
• Hard examples for resolution

  1987cited by this paper
• The Intractability of Resolution

  1985cited by this paper
• Random Constraint Satisfaction a More Accurate Picture

  year unknowncited by this paper

• How Random CSPs Fool Hierarchies: II

  2025cites this paper
• The periodic structure of local consistency

  2024cites this paper
• Promise Constraint Satisfaction and Width

  2021cites this paper
• The Freezing Threshold for k-Colourings of a Random Graph

  2018cites this paper
• Resolution Complexity of Random Constraint Satisfaction Problems

  2016cites this paper
• Space proof complexity for random 3-CNFs

  2015influential citation
• Inside the clustering threshold for random linear equations

  2013cites this paper
• The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem

  2012influential citation
• The freezing threshold for k-colourings of a random graph

  2012cites this paper
• A general model and thresholds for random constraint satisfaction problems

  2012cites this paper
• Frozen variables in random boolean constraint satisfaction problems

  2012cites this paper
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT

  2012cites this paper
• The solution space geometry of random linear equations

  2011cites this paper
• Consistency and Random Constraint Satisfaction Models

  2011influential citation
• Exact phase transition of backtrack-free search with implications on the power of greedy algorithms

  2008cites this paper
• Universality in two-dimensional enhancement percolation

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

  2008influential citation
• When does the giant component bring unsatisfiability?

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

  2008cites this paper
• MAX k-CUT and approximating the chromatic number of random graphs

  2006cites this paper
• The satisfiability threshold for randomly generated binary constraint satisfaction problems

  2006cites this paper
• Handbook of Constraint Programming

  2006cites this paper
• Sharp thresholds for constraint satisfaction problems and homomorphisms

  2006cites this paper
• Randomness and Structure

  2006cites this paper
• Spines of random constraint satisfaction problems: definition and connection with computational complexity

  2005cites this paper
• Spines of Random Constraint Satisfaction Problems: Definition and Impact on Computational Complexity

  2004cites this paper
• A Random Constraint Satisfaction Problem That Seems Hard for DPLL

  2004cites this paper
• The exact satisfiability threshold for a potentially intractable random constraint satisfaction problem

  2004cites this paper
• Consistency and Random Constraint Satisfaction Models with a High Constraint Tightness

  2004influential citation
• A Theoretical Comparison of Resolution Proof Systems for CSP Algorithms

  2004cites this paper
• Proceedings 44th IEEE Symposium on Foundations of Computer Science - FOCS 2003

  2003cites this paper
• Resolution complexity of random constraint satisfaction problems: Another half of the story

  2003influential citation
• Many hard examples in exact phase transitions

  2003cites this paper
• Resolution and Constraint Satisfaction

  2003cites this paper
• Chapter 18 Randomness and Structure

  year unknowncites this paper