An Algebraic Characterization of Testable Boolean CSPs

DOI10.1007/978-3-642-39206-1_11zbMath1336.68282OpenAlexW22128777MaRDI QIDQ5326555

Arnab Bhattacharyya, Yuichi Yoshida

Publication date: 6 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-39206-1_11

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (4)

Testing list \(H\)-homomorphisms ⋮ Unnamed Item ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ A characterization of constant‐sample testable properties

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of satisfiability problems: Refining Schaefer's theorem
• On the algebraic structure of combinatorial problems
• Complexity of generalized satisfiability counting problems
• A combinatorial characterization of the testable graph properties
• Graph limits and parameter testing
• Property testing and its connection to learning and approximation
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Monotonicity testing over general poset domains
• Testing st-Connectivity
• Undirected connectivity in log-space
• Robust Characterizations of Polynomials with Applications to Program Testing
• Property Testing of Massively Parametrized Problems – A Survey
• A unified framework for testing linear‐invariant properties
• The complexity of satisfiability problems
• Some 3CNF Properties Are Hard to Test
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

This page was built for publication: An Algebraic Characterization of Testable Boolean CSPs