Constraints, MMSNP and expander relational structures
From MaRDI portal
Publication:2439829
DOI10.1007/s00493-013-2405-4zbMath1313.05274arXiv0706.1701MaRDI 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
05C65: Hypergraphs
05C38: Paths and cycles
05C15: Coloring of graphs and hypergraphs
05C12: Distance in graphs
68W20: Randomized algorithms
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Unnamed Item, A Dichotomy for First-Order Reducts of Unary Structures, A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP, Unnamed Item, Uniform Constraint Satisfaction Problems and Database Theory, Constraint Satisfaction Problems with Infinite Templates, Dualities and dual pairs in Heyting algebras, In praise of homomorphisms, A new line of attack on the dichotomy conjecture, A combinatorial constraint satisfaction problem dichotomy classification conjecture, A surprising permanence of old motivations (a not-so-rigid story), On the complexity of \(\mathbb{H}\)-coloring for special oriented trees, ASNP: a tame fragment of existential second-order logic, High girth hypergraphs with unavoidable monochromatic or rainbow edges, Fractal property of the graph homomorphism order, Forbidden lifts (NP and CSP for combinatorialists), Non-bipartite pairs of 3-connected graphs are highly Ramsey-infinite, On the CSP Dichotomy Conjecture, NP for Combinatorialists
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