Towards a proof of the 2-to-1 games conjecture?
From MaRDI portal
Publication:5230304
DOI10.1145/3188745.3188804zbMath1429.68076OpenAlexW2809286765MaRDI QIDQ5230304
Irit Dinur, Subhash A. Khot, Guy Kindler, Dor Minzer, Shmuel Safra
Publication date: 22 August 2019
Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3188745.3188804
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (18)
Log-Sobolev inequality for the multislice, with applications ⋮ Exploiting low-rank structure in semidefinite programming by approximate operator splitting ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ Approximating power node-deletion problems ⋮ Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ Unnamed Item ⋮ 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 ⋮ High order random walks: beyond spectral gap ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On non-optimally expanding sets in Grassmann graphs ⋮ UG-hardness to NP-hardness by losing half ⋮ Imperfect gaps in Gap-ETH and PCPs ⋮ Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
This page was built for publication: Towards a proof of the 2-to-1 games conjecture?
