On non-optimally expanding sets in Grassmann graphs

DOI10.1145/3188745.3188806zbMATH Open1429.68077OpenAlexW2809340088MaRDI QIDQ5230352FDOQ5230352

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

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

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)

Cited In (26)

• Title not available (Why is that?)
• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Title not available (Why is that?)
• Inapproximability of unique games in fixed-point logic with counting
• Conditional dichotomy of Boolean ordered promise CSPs
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
• Hypercontractivity for global functions and sharp thresholds
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• Three candidate plurality is stablest for small correlations
• Title not available (Why is that?)
• Mathematics of computation through the lens of linear equations and lattices
• On non-optimally expanding sets in Grassmann graphs
• Online learning for min-max discrete problems
• 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
• Title not available (Why is that?)
• 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)