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

(34)

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

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)