Constraints, MMSNP and expander relational structures

DOI10.1007/s00493-013-2405-4zbMath1313.05274arXiv0706.1701OpenAlexW2041384065MaRDI QIDQ2439829

Gábor Kun

Publication date: 17 March 2014

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

polynomial-time algorithmgirthrelational structureexpanderMMSNPCSP-class

Mathematics Subject Classification ID

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

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