Chicago Journal of Theoretical Computer Science

Volume 2023

Article 2

Published by the Department of Computer Science, The University of Chicago.

A Family of Dictatorship Tests with Perfect Completeness for 2–to–2 Label Cover

Joshua Brakensiek
Department of Computer Science
Stanford University
Stanford, CA
jbrakens AT cs DOT stanford DOT edu


Venkatesan Guruswami
Department of EECS and Simons Institute for the Theory of Computing, University of California Berkeley
Berkeley, CA
venktag AT berkeley DOT edu

June 30, 2023


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.

DOI: 10.4086/cjtcs.2023.002

[] Volume 2023, Article 1 [] Article 3
[back] Volume 2023 [back] Published articles
[CJCTS home]