Inapproximability of counting hypergraph colourings
From MaRDI portal
Cites work
- A constructive proof of the general Lovász local lemma
- A constructive proof of the Lovász local lemma
- A parallel algorithmic version of the local lemma
- An algorithmic approach to the Lovász local lemma. I
- Approximate counting, the Lovász local lemma, and inference in graphical models
- Approximation via Correlation Decay When Strong Spatial Mixing Fails
- Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
- Coloring simple hypergraphs
- Computational transition at the uniqueness threshold
- Correlation decay up to uniqueness in spin systems
- Counting hypergraph colorings in the local lemma regime
- Counting in two-spin models on \(d\)-regular graphs
- Fast mixing for independent sets, colorings, and other models on trees
- Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime
- scientific article; zbMATH DE number 5764785 (Why is no real title available?)
- scientific article; zbMATH DE number 3492718 (Why is no real title available?)
- scientific article; zbMATH DE number 1332666 (Why is no real title available?)
- scientific article; zbMATH DE number 1775440 (Why is no real title available?)
- Inapproximability after uniqueness phase transition in two-spin systems
- Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region
- Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
- On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}
- On Counting Independent Sets in Sparse Graphs
- On the hardness of sampling independent sets beyond the tree threshold
- On weighted vs unweighted versions of combinatorial optimization problems
- One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
- Perfect Matchings in Random r-regular, s-uniform Hypergraphs
- Random generation of combinatorial structures from a uniform distribution
- Rapid mixing of hypergraph independent sets
- Sampling colorings and independent sets of random regular bipartite graphs in the non-uniqueness region
- Sampling constraint satisfaction solutions in the local lemma regime
- Satisfiability thresholds for regular occupation problems
- Some APX-completeness results for cubic graphs
- Spectral independence, coupling, and the spectral gap of the Glauber dynamics
- The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
- The local lemma Is asymptotically tight for SAT
- Uniform sampling through the Lovász local lemma
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
Cited in
(2)
This page was built for publication: Inapproximability of counting hypergraph colourings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7023434)
