An algebraic characterization of testable Boolean CSPs

DOI10.1007/978-3-642-39206-1_11MaRDI QIDQ5326555zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Constant-query testability of assignments to constraint satisfaction problems
• Property testers for dense constraint satisfaction programs on finite domains
• Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
• A new line of attack on the dichotomy conjecture
• Asking the Metaquestions in Constraint Tractability

Cites work

• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• A combinatorial characterization of the testable graph properties, it's all about regularity
• A unified framework for testing linear-invariant properties
• Algebraic property testing: the role of invariance
• Complexity of generalized satisfiability counting problems
• Graph limits and parameter testing
• scientific article; zbMATH DE number 1670830 (Why is no real title available?)
• Monotonicity testing over general poset domains
• On the algebraic structure of combinatorial problems
• Property testing and its connection to learning and approximation
• Property testing of massively parametrized problems -- a survey
• Robust Characterizations of Polynomials with Applications to Program Testing
• Some 3CNF Properties Are Hard to Test
• Testing st-Connectivity
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of satisfiability problems
• The complexity of satisfiability problems: Refining Schaefer's theorem
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Undirected connectivity in log-space

Cited in

(6)

• Homogenization of parabolic equations with an arbitrary number of scales in both space and time
• Testing list H-homomorphisms
• Constant-query testability of assignments to constraint satisfaction problems
• A characterization of constant-sample testable properties
• Learnability of solutions to conjunctive queries
• Testing spreading behavior in networks with arbitrary topologies

This page was built for publication: An algebraic characterization of testable Boolean CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326555)