Pairs of SAT Assignments and Clustering in Random Boolean Formulae

No abstract is available for this paper.

• Publication year

  2005

• Venue

  Unknown venue

• Publication date

  2005-06-02

• 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.

• Clustering of solutions in the random satisfiability problem

  2005cited by this paper
• Information Theory, Inference, and Learning Algorithms

  2004cited by this paper
• Facilitated spin models on Bethe lattice: Bootstrap percolation, mode-coupling transition and glassy dynamics

  2004cited by this paper
• Adaptability and "intermediate phase" in randomly connected networks.

  2004cited by this paper
• Frozen glass phase in the multi-index matching problem.

  2004cited by this paper
• THE THRESHOLD FOR RANDOM k-SAT IS 2 log 2−O(k)

  2004cited by this paper
• The threshold for random k-SAT is 2^k log 2 - O(k)

  2004cited by this paper
• Threshold values of random K‐SAT from the cavity method

  2003influential reference
• Polynomial iterative algorithms for coloring and analyzing random graphs.

  2003cited by this paper
• Instability of one-step replica-symmetry-broken phase in satisfiability problems

  2003cited by this paper
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses

  2003cited by this paper
• A Study of Pure Random Walk on Random Satisfiability Problems with "Physical" Methods

  2003cited by this paper
• Two Solutions to Diluted p-Spin Models and XORSAT Problems

  2003cited by this paper
• Rigorous decimation-based construction of ground pure states for spin-glass models on random lattices.

  2002cited by this paper
• Random K-satisfiability problem: from an analytic solution to an efficient algorithm.

  2002cited by this paper
• Analytic and Algorithmic Solution of Random Satisfiability Problems

  2002cited by this paper
• Coloring random graphs

  2002cited by this paper
• The asymptotic order of the random k-SAT threshold

  2002cited by this paper
• Dynamic phase transition for decoding algorithms.

  2002cited by this paper
• The Cavity Method at Zero Temperature

  2002cited by this paper
• Survey propagation: An algorithm for satisfiability

  2002cited by this paper
• The glassy phase of Gallager codes

  2001cited by this paper
• The Bethe lattice spin glass revisited

  2000cited by this paper
• Determining computational complexity from characteristic ‘phase transitions’

  1999cited by this paper
• Sharp thresholds of graph properties, and the -sat problem

  1999cited by this paper
• A General Upper Bound for the Satisfiability Threshold of Random r-SAT Formulae

  1997cited by this paper
• Analysis of Two Simple Heuristics on a Random Instance of k-SAT

  1996cited by this paper
• A better upper bound for the unsatisfiability threshold

  1996influential reference
• Critical Behavior in the Satisfiability of Random Boolean Expressions

  1994cited by this paper
• Asymptotic estimates of Stirling numbers

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

  1990cited by this paper
• The complexity of theorem-proving procedures

  1971influential reference
• Information Theory and Reliable Communication

  1969influential reference
• Information Theory and Reliable Communication

  1968cited by this paper

• From algorithms to connectivity and back: finding a giant component in random k-SAT

  2022cites this paper
• The large deviations of the whitening process in random constraint satisfaction problems

  2016influential citation
• A statistical physics approach to different problems in network theory

  2015cites this paper
• Inside the clustering window for random linear equations

  2015cites this paper
• Minimal Contagious Sets in Random Regular Graphs

  2014cites this paper
• Minimal Contagious Sets in Random Regular Graphs

  2014cites this paper
• Mean-field disordered systems : glasses and optimization problems, classical and quantum

  2013cites this paper
• Inside the clustering threshold for random linear equations

  2013cites this paper
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective

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

  2011cites this paper
• Gibbs Measures and Phase Transitions on Sparse Random Graphs

  2009cites this paper
• The structure of the set of satisfying assignments for a random k-CNF

  2008influential citation
• Solution clustering in random satisfiability

  2008cites this paper
• Statistical Physics of Hard Optimization Problems

  2008cites this paper
• Horn Upper Bounds and Renaming

  2007cites this paper
• Satisfying assignments of Random Boolean CSP: Clusters and Overlaps

  2007cites this paper
• Satisfying Assignments of Random Boolean Constraint Satisfaction Problems: Clusters and Overlaps

  2007cites this paper
• Why almost all k-CNF formulas are easy

  2007cites this paper
• Finite size scaling for the core of large random hypergraphs

  2007cites this paper
• On the random satisfiable 3 CNF process

  2007cites this paper
• Why almost all satisfiable $k$-CNF formulas are easy

  2007cites this paper
• Why Almost All k-Colorable Graphs Are Easy to Color

  2007cites this paper
• Visualizing Survey Propagation in 3-SAT Factor Graphs

  2006cites this paper
• On the solution-space geometry of random constraint satisfaction problems

  2006cites this paper
• Barriers and local minima in energy landscapes of stochastic local search

  2006cites this paper
• Geometrical organization of solutions to random linear Boolean equations

  2006cites this paper
• Why almost all satisfiable k -CNF formulas are easy

  year unknowncites this paper