CJTCS Volume 2023 Article 2

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

and

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

Abstract

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.

The article: PDF (268 KB)
Source material: ZIP (94 KB)
BibTeX entry for this article (268 bytes)

Submitted August 23 2019, revised June 23, 2023, published June 30, 2023.

DOI: 10.4086/cjtcs.2023.002

Licensed under a Creative Commons Attribution License

Volume 2023, Article 1

Article 3

Volume 2023 [back]

Published articles