Random Instances of Problems in NP – Algorithms and Statistical Physics
DOI10.1007/978-3-319-24024-4_13zbMath1331.68103OpenAlexW2213180549MaRDI QIDQ3464473
Publication date: 27 January 2016
Published in: Algorithms, Probability, Networks, and Games (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-24024-4_13
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) General topics in the theory of algorithms (68W01) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimization by Simulated Annealing
- Decay of correlations for the hardcore model on the \(d\)-regular random graph
- On the Potts antiferromagnet on random graphs
- On the chromatic number of random regular graphs
- On the independence number of random graphs
- Loss networks
- Gibbs measures and phase transitions
- Disagreement percolation in the study of Markov fields
- Learning low-level vision
- Maximum independent sets on random regular graphs
- Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
- Improved bounds for sampling colorings
- Switching Colouring of G(n,d/n) for Sampling up to Gibbs Uniqueness Threshold
- The solution of some random NP-hard problems in polynomial expected time
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Independent Sets in Random Graphs from the Weighted Second Moment Method
- Reconstruction and Clustering in Random Constraint Satisfaction Problems
- Randomly coloring sparse random graphs with fewer colors than the maximum degree
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- On independent sets in random graphs
- Randomly coloring planar graphs with fewer colors than the maximum degree
- The Glauber Dynamics for Colourings of Bounded Degree Trees
- Large Cliques Elude the Metropolis Process
- On colouring random graphs
- Approximating the unsatisfiability threshold of random formulas
- Sharp thresholds of graph properties, and the $k$-sat problem
- Factor graphs and the sum-product algorithm
- The capacity of low-density parity-check codes under message-passing decoding
- The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
- A second threshold for the hard‐core model on a Bethe lattice
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
- The asymptotic k-SAT threshold
- Satisfiability threshold for random regular NAE-SAT
- Survey propagation: An algorithm for satisfiability
- Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees
- Gibbs states and the set of solutions of random constraint satisfaction problems
- A Better Algorithm for Random k-SAT
- Catching the k-NAESAT threshold
- Strong Spatial Mixing with Fewer Colors for Lattice Graphs
- Going after the k-SAT threshold
- The Traveling-Salesman Problem and Minimum Spanning Trees
- On the solution‐space geometry of random constraint satisfaction problems
- The two possible values of the chromatic number of a random graph
- Kiyoshi Itô (1915--2008)
This page was built for publication: Random Instances of Problems in NP – Algorithms and Statistical Physics
