Constraints, MMSNP and expander relational structures

DOI10.1007/s00493-013-2405-4zbMath1313.05274arXiv0706.1701MaRDI 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 algorithm; girth; relational structure; expander; MMSNP; CSP-class

Mathematics Subject Classification ID

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