scientific article; zbMATH DE number 7561583

DOI10.4230/LIPIcs.ICALP.2019.90MaRDI QIDQ5091251

Matija Pasch, Konstantinos D. Panagiotou

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1811.00991

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

constraint satisfaction problemsmall subgraph conditioningcontraction coefficientfirst momentsecond momentreplica symmetric

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The phase transition in random regular exact cover
• 3-star factors in random \(d\)-regular graphs
• The asymptotic \(k\)-SAT threshold
• On the chromatic number of random \(d\)-regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Information-theoretic thresholds from the cavity method
• Charting the replica symmetric phase
• Quasi-Eulerian hypergraphs
• Maximum independent sets on random regular graphs
• Proof of the Satisfiability Conjecture for Large k
• Constraint satisfaction: random regular k-SAT
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
• Circular coloring of random graphs: statistical physics investigation
• A new look at survey propagation and its generalizations
• Relations between average case complexity and approximation complexity
• Information, Physics, and Computation
• Bounds on conditional probabilities with applications in multi-user communication
• Community Detection and Stochastic Block Models
• Phase transitions in theq-coloring of random hypergraphs
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs
• Generating and Counting Hamilton Cycles in Random Regular Graphs
• Survey propagation: An algorithm for satisfiability
• Spatially Coupled Ensembles Universally Achieve Capacity Under Belief Propagation
• Planting Colourings Silently
• On the existence of a factor of degree one of a connected random graph
• Bicolouring random hypergraphs
• Satisfiability threshold for random regular \textsc{nae-sat}

This page was built for publication: