On independent sets, 2-to-2 games, and Grassmann graphs

DOI10.1145/3055399.3055432zbMath1370.68130OpenAlexW2625656873MaRDI QIDQ4978004

Dor Minzer, Shmuel Safra, Subhash A. Khot

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3055399.3055432

zbMATH Keywords

PCPunique gamesvertex-cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (14)

Log-Sobolev inequality for the multislice, with applications ⋮ Boolean degree 1 functions on some classical association schemes ⋮ Approximating power node-deletion problems ⋮ Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ New tools and connections for exponential-time approximation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On non-optimally expanding sets in Grassmann graphs ⋮ Upper and lower degree-constrained graph orientation with minimum penalty ⋮ UG-hardness to NP-hardness by losing half

This page was built for publication: On independent sets, 2-to-2 games, and Grassmann graphs