Published by the Department of Computer Science, The University of Chicago.
Department of EECS and Simons Institute for the Theory of Computing, University of California Berkeley
venktag AT berkeley DOT edu
We give a family of dictatorship tests with perfect completeness and low-soundness for 2–to–2 constraints. The associated 2–to–2 conjecture has been the basis of a few inapproximability results with perfect completeness. Our result provides some indication of the expressiveness and non-triviality of 2–to–2 constraints, given the close connections between dictatorship tests and satisfiability and approximability of CSPs.
Submitted August 23 2019, revised June 23, 2023, published June 30, 2023.