On non-optimally expanding sets in Grassmann graphs

DOI10.1007/S11856-021-2164-7MaRDI QIDQ2048867zbMATH OpenOpenAlexFDO

Authors Dor Minzer, Irit Dinur, Subhash Khot, Guy Kindler, Shmuel Safra

Publication date 24 August 2021

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11856-021-2164-7

Mathematics Subject Classification ID

Theory of computing (68Qxx) Graph theory (05Cxx) Algebraic combinatorics (05Exx)

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
• Graph expansion and the unique games conjecture
• On independent sets, 2-to-2 games, and Grassmann graphs

Cites work

• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 1775415 (Why is no real title available?)
• A PCP characterization of NP with optimal amortized query complexity
• A new point of NP-hardness for unique games
• A positive combinatorial formula for the complexity of the \(q\)-analog of the \(n\)-cube
• A two-prover one-round game with strong soundness
• An orthogonal basis for functions over a slice of the Boolean hypercube
• Erdős-Ko-Rado theorems. Algebraic approaches
• Friedgut-Kalai-Naor theorem for slices of the Boolean cube
• Harmonicity and invariance on slices of the Boolean cube
• Invariance principle on the slice
• On Certain Sets of Integers
• On independent sets, 2-to-2 games, and Grassmann graphs
• On non-optimally expanding sets in Grassmann graphs
• On the power of unique 2-prover 1-round games
• Query efficient PCPs with perfect completeness
• Simple analysis of graph tests for linearity and PCP
• Small-set expansion in shortcode graph and the 2-to-2 conjecture
• Some optimal inapproximability results
• The Erdős-Ko-Rado theorem for vector spaces
• The Goldman-Rota identity and the Grassmann scheme
• Towards a proof of the 2-to-1 games conjecture?

Cited in

(3)

• Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
• Small-set expansion in shortcode graph and the 2-to-2 conjecture
• 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 Q2048867)