The replica symmetric phase of random constraint satisfaction problems (Q4993097)

scientific article; zbMATH DE number 7359158

Language	Label	Description	Also known as
English	The replica symmetric phase of random constraint satisfaction problems	scientific article; zbMATH DE number 7359158

Statements

instance of

scholarly article

0 references

title

The replica symmetric phase of random constraint satisfaction problems (English)

0 references

zbMATH Open document ID

1504.68152

0 references

DOI

10.1017/S0963548319000440

0 references

author

Amin Coja-Oghlan

0 references

Tobias Kapetanopoulos

0 references

Noela Müller

0 references

published in

Combinatorics, Probability and Computing

0 references

publication date

15 June 2021

0 references

full work available at URL

https://arxiv.org/abs/1802.09311

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

MaRDI publication profile

0 references

arXiv ID

1802.09311

0 references

cites work

Proof of the Achievability Conjectures for the General Stochastic Block Model

0 references

Q2768371

0 references

Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold

0 references

The two possible values of the chromatic number of a random graph

0 references

The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)

0 references

A Spectral Technique for Coloring Random 3-Colorable Graphs

0 references

Constraining the clustering transition for colorings of sparse random graphs

0 references

Algebraic Attacks against Random Local Functions and Their Countermeasures

0 references

The satisfiability threshold for random linear equations

0 references

Hypergraph coloring up to condensation

0 references

Rigid Colorings of Hypergraphs and Contiguity

0 references

Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models

0 references

Harnessing the Bethe free energy

0 references

Planting Colourings Silently

0 references

The condensation phase transition in random graph coloring

0 references

Combinatorial approach to the interpolation method and scaling limits in sparse random graphs

0 references

Q2743189

0 references

Q4012216

0 references

Q4228436

0 references

Upper-bounding the $k$-colorability threshold by counting covers

0 references

Charting the replica symmetric phase

0 references

On the Potts antiferromagnet on random graphs

0 references

Information-theoretic thresholds from the cavity method

0 references

Catching the k-NAESAT threshold

0 references

The asymptotic $k$-SAT threshold

0 references

The Number of Satisfying Assignments of Random Regulark-SAT Formulas

0 references

The condensation transition in random hypergraph 2-coloring

0 references

Tight Thresholds for Cuckoo Hashing via XORSAT

0 references

Proof of the Satisfiability Conjecture for Large k

0 references

Satisfiability threshold for random regular \textsc{nae-sat}

0 references

The 3-XORSAT threshold.

0 references

The solution of some random NP-hard problems in polynomial expected time

0 references

On the chromatic number of a random hypergraph

0 references

Q3286850

0 references

Relations between average case complexity and approximation complexity

0 references

On the Complexity of Random Satisfiability Problems with Planted Solutions

0 references

Replica bounds for optimization problems and diluted spin systems

0 references

Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region

0 references

Limits of local algorithms over sparse random graphs

0 references

Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem

0 references

A threshold for unsatisfiability

0 references

Candidate One-Way Functions Based on Expander Graphs

0 references

Foundations of quantization for probability distributions

0 references

Quantization for Probability Measures in the Prokhorov Metric

0 references

Broken replica symmetry bounds in the mean field spin glass model

0 references

Random Graphs and Complex Networks

0 references

Random Regular Graphs: Asymptotic Distributions and Contiguity

0 references

Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes

0 references

Semirandom Models as Benchmarks for Coloring Algorithms

0 references

Q3194806

0 references

Gibbs states and the set of solutions of random constraint satisfaction problems

0 references

Quiet Planting in the Locked Constraint Satisfaction Problems

0 references

Information, Physics, and Computation

0 references

The freezing threshold for k-colourings of a random graph

0 references

Reconstruction and Clustering in Random Constraint Satisfaction Problems

0 references

The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness

0 references

Reconstruction and estimation in the planted partition model

0 references

Bounds for diluted mean-fields spin glass models

0 references

The Satisfiability Threshold fork-XORSAT

0 references

On the Number of Solutions in Random Graphk-Colouring

0 references

Almost all cubic graphs are Hamiltonian

0 references

The complexity of satisfiability problems

0 references

Sharp concentration of the chromatic number on random graphs $G_{n,p}$

0 references

Reconstruction for the Potts model

0 references

OpenAlex ID

W3098834697

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:4993097