Constraints, MMSNP and expander relational structures
From MaRDI portal
Publication:2439829
DOI10.1007/s00493-013-2405-4zbMath1313.05274arXiv0706.1701OpenAlexW2041384065MaRDI QIDQ2439829
Publication date: 17 March 2014
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0706.1701
Hypergraphs (05C65) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (19)
In praise of homomorphisms ⋮ Fractal property of the graph homomorphism order ⋮ Dualities and dual pairs in Heyting algebras ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ NP for Combinatorialists ⋮ A new line of attack on the dichotomy conjecture ⋮ Forbidden lifts (NP and CSP for combinatorialists) ⋮ Non-bipartite pairs of 3-connected graphs are highly Ramsey-infinite ⋮ On the CSP Dichotomy Conjecture ⋮ A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP ⋮ Unnamed Item ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture ⋮ A Dichotomy for First-Order Reducts of Unary Structures ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ Constraint Satisfaction Problems with Infinite Templates ⋮ ASNP: a tame fragment of existential second-order logic ⋮ Unnamed Item ⋮ High girth hypergraphs with unavoidable monochromatic or rainbow edges
Cites Work
- Unnamed Item
- Unnamed Item
- Explicit constructions of Ramanujan complexes of type \(\widetilde A_d\).
- Ramanujan complexes of type \(\widetilde A_d\)
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- Sorting in \(c \log n\) parallel steps
- Ramanujan graphs
- A short proof of the existence of highly chromatic hypergraphs without short cycles
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Graph Theory and Probability
- Expander graphs and their applications
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- On chromatic number of finite set-systems
- Colorings and homomorphisms of degenerate and bounded degree graphs
This page was built for publication: Constraints, MMSNP and expander relational structures