Random instances of problems in NP -- algorithms and statistical physics

DOI10.1007/978-3-319-24024-4_13MaRDI QIDQ3464473zbMATH OpenOpenAlexFDO

Authors Charilaos Efthymiou

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

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topics in the theory of algorithms (68W01)

Recommendations

• Phase transitions of random constraint satisfaction problems
• Complexity-theoretic models of phase transitions in search problems
• Phase transitions in discrete structures
• Phase transition and finite-size scaling in the vertex-cover problem
• Statistical mechanics methods and phase transitions in optimization problems

Cites work

• scientific article; zbMATH DE number 48812 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1303602 (Why is no real title available?)
• scientific article; zbMATH DE number 1380613 (Why is no real title available?)
• scientific article; zbMATH DE number 5279368 (Why is no real title available?)
• scientific article; zbMATH DE number 6297817 (Why is no real title available?)
• scientific article; zbMATH DE number 6469177 (Why is no real title available?)
• A better algorithm for random \(k\)-SAT
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• A second threshold for the hard‐core model on a Bethe lattice
• Approximating the unsatisfiability threshold of random formulas
• Catching the \(k\)-NAESAT threshold
• Counting good truth assignments of random k-SAT formulae
• Decay of correlations for the hardcore model on the d-regular random graph
• Disagreement percolation in the study of Markov fields
• Factor graphs and the sum-product algorithm
• Gibbs measures and phase transitions
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Going after the k-SAT threshold
• Improved bounds for sampling colorings
• Independent sets in random graphs from the weighted second moment method
• Kiyoshi Itô (1915--2008)
• Large Cliques Elude the Metropolis Process
• Learning low-level vision
• Loss networks
• Maximum independent sets on random regular graphs
• On colouring random graphs
• On the Potts antiferromagnet on random graphs
• On the chromatic number of random regular graphs
• On the independence number of random graphs
• On the solution-space geometry of random constraint satisfaction problems
• Optimization by simulated annealing
• Phase transition for Glauber dynamics for independent sets on regular trees
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Reconstruction and clustering in random constraint satisfaction problems
• Reconstruction/non-reconstruction thresholds for colourings of general Galton-Watson trees
• Satisfiability threshold for random regular NAE-SAT
• Sharp thresholds of graph properties, and the k-sat problem
• Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• Survey propagation: An algorithm for satisfiability
• Switching colouring of G(n,d/n) for sampling up to Gibbs uniqueness threshold
• The Glauber Dynamics for Colourings of Bounded Degree Trees
• The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The asymptotic \(k\)-SAT threshold
• The capacity of low-density parity-check codes under message-passing decoding
• The condensation phase transition in random graph coloring
• The solution of some random NP-hard problems in polynomial expected time
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The two possible values of the chromatic number of a random graph

Cited in

(12)

• Notes on computational-to-statistical gaps: predictions using statistical physics
• Phase transitions in discrete structures
• scientific article; zbMATH DE number 2063192 (Why is no real title available?)
• On percolation and NP-hardness
• Structure vs combinatorics in computational complexity
• Complexity-theoretic models of phase transitions in search problems
• Experimental study of the random 2+p-COL problem
• Phase transition in a random NK landscape model
• Disordered systems insights on computational hardness
• Principles and Practice of Constraint Programming – CP 2004
• scientific article; zbMATH DE number 3909744 (Why is no real title available?)
• scientific article; zbMATH DE number 436075 (Why is no real title available?)

This page was built for publication: Random instances of problems in NP -- algorithms and statistical physics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3464473)