On non-optimally expanding sets in Grassmann graphs

DOI10.1145/3188745.3188806MaRDI QIDQ5230352zbMATH OpenOpenAlexFDO

Authors Irit Dinur, Subhash 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.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)

Recommendations

• On non-optimally expanding sets in Grassmann graphs
• Small-set expansion in shortcode graph and the 2-to-2 conjecture
• On the proof of the 2-to-2 games conjecture
• Towards a proof of the 2-to-1 games conjecture?
• Graph expansion and the unique games conjecture

Cited in

(28)

• High order random walks: beyond spectral gap
• Boolean function analysis on high-dimensional expanders
• On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
• On the proof of the 2-to-2 games conjecture
• Log-Sobolev inequality for the multislice, with applications
• LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY
• Small-set expansion in shortcode graph and the 2-to-2 conjecture
• Approximate graph colouring and the hollow shadow
• The power of unentangled quantum proofs with non-negative amplitudes
• Boolean function analysis on high-dimensional expanders
• UG-hardness to NP-hardness by losing half
• scientific article; zbMATH DE number 7561741 (Why is no real title available?)
• Towards a proof of the 2-to-1 games conjecture?
• scientific article; zbMATH DE number 7559077 (Why is no real title available?)
• Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
• scientific article; zbMATH DE number 7650072 (Why is no real title available?)
• Inapproximability of unique games in fixed-point logic with counting
• Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
• Mathematics of computation through the lens of linear equations and lattices
• scientific article; zbMATH DE number 7716602 (Why is no real title available?)
• Hypercontractivity for global functions and sharp thresholds
• High order random walks: beyond spectral gap
• Conditional dichotomy of Boolean ordered promise CSPs
• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• Three candidate plurality is stablest for small correlations
• Online learning for min-max discrete problems
• On non-optimally expanding sets in Grassmann graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230352)