Testing list \(H\)-homomorphisms

DOI10.1007/s00037-014-0093-0zbMath1353.68139OpenAlexW2462341721MaRDI QIDQ347111

Yuichi Yoshida

Publication date: 30 November 2016

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-014-0093-0

zbMATH Keywords

constraint satisfaction problemsuniversal algebraproperty testinglist \(H\)-homomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

The spaces of Siegel cusp forms of degree two and the representation of \(\mathrm{Sp}(2,\mathbb F_ p)\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing the \((s,t)\) connectivity of graphs and digraphs
• The complexity of the list homomorphism problem for graphs
• \(H\)-coloring dichotomy revisited
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• A sublinear bipartiteness tester for bounded degree graphs
• List homomorphisms and circular arc graphs
• Combinatorial problems raised from 2-semilattices
• Introduction to Testing Graph Properties
• Property testing and its connection to learning and approximation
• On the query complexity of testing orientations for being Eulerian
• Near-Unanimity Functions and Varieties of Reflexive Graphs
• Monotonicity testing over general poset domains
• Testing st-Connectivity
• The structure of finite algebras
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Testing satisfiability
• Bi‐arc graphs and the complexity of list homomorphisms
• Property Testing of Massively Parametrized Problems – A Survey
• A unified framework for testing linear‐invariant properties
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• lgorithmic and Analysis Techniques in Property Testing
• An Algebraic Characterization of Testable Boolean CSPs
• Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
• Recent Results on the Algebraic Approach to the CSP
• Some 3CNF Properties Are Hard to Test
• Property testing in bounded degree graphs

This page was built for publication: Testing list \(H\)-homomorphisms