Constant-Query Testability of Assignments to Constraint Satisfaction Problems

DOI10.1137/18M121085XzbMath1430.68439WikidataQ127870181 ScholiaQ127870181MaRDI QIDQ5232319

Yuichi Yoshida, Hubie Chen, Matthew A. Valeriote

Publication date: 2 September 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

constraint satisfaction problemsproperty testingmassively parameterized model

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Randomized algorithms (68W20) Relational systems, laws of composition (08A02) Computational aspects of satisfiability (68R07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial interpolation and the Chinese remainder theorem for algebraic systems
• Constraints, consistency and closure
• THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA
• The collapse of the bounded width hierarchy
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• Complexity of conservative constraint satisfaction problems
• The complexity of global cardinality constraints
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• The Complexity of Finite-Valued CSPs
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Sublinear Time Algorithms
• Sherali-Adams Relaxations for Valued CSPs
• Monotonicity testing over general poset domains
• On the power of unique 2-prover 1-round games
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• Decidability problem for finite Heyting algebras
• The structure of finite algebras
• Property Testing of Massively Parametrized Problems – A Survey
• Asking the Metaquestions in Constraint Tractability
• The shape of congruence lattices
• lgorithmic and Analysis Techniques in Property Testing
• An Algebraic Characterization of Testable Boolean CSPs
• Tractability and Learnability Arising from Algebras with Few Subpowers
• The complexity of the counting constraint satisfaction problem
• Some 3CNF Properties Are Hard to Test

This page was built for publication: Constant-Query Testability of Assignments to Constraint Satisfaction Problems