On non-optimally expanding sets in Grassmann graphs

DOI10.1145/3188745.3188806zbMath1429.68077OpenAlexW2809340088MaRDI QIDQ5230352

Guy Kindler, Irit Dinur, Subhash A. Khot, 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.3188806

zbMATH Keywords

Grassmann graphPCPunique games2-to-2 games

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (21)

Log-Sobolev inequality for the multislice, with applications ⋮ Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs ⋮ Online learning for min-max discrete problems ⋮ On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs ⋮ Hypercontractivity for global functions and sharp thresholds ⋮ 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 ⋮ Unnamed Item ⋮ LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Three candidate plurality is stablest for small correlations ⋮ 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 ⋮ Tight inapproximability of minimum maximal matching on bipartite graphs and related problems

This page was built for publication: On non-optimally expanding sets in Grassmann graphs