Pseudorandom sets in Grassmann graph have near-perfect expansion
From MaRDI portal
Publication:6101019
DOI10.4007/annals.2023.198.1.1OpenAlexW4378449969MaRDI QIDQ6101019
Dor Minzer, Shmuel Safra, Subhash A. Khot
Publication date: 31 May 2023
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4007/annals.2023.198.1.1
Related Items
Approximating power node-deletion problems ⋮ Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry ⋮ Incomplete list setting of the hospitals/residents problem with maximally satisfying lower quotas ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ On the partial vertex cover problem in bipartite graphs -- a parameterized perspective ⋮ Safe sets and in-dominating sets in digraphs ⋮ Hypercontractivity on the symmetric group
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the hardness of approximating minimum vertex cover
- The jackknife estimate of variance
- Applications of ANOVA type decompositions for comparisons of conditional variance statistics including jackknife estimates
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Towards a proof of the Fourier-entropy conjecture?
- On the hardness of approximating Multicut and Sparsest-Cut
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- $\mathcal{NP}$-Hardness of Approximately Solving Linear Equations over Reals
- Graph expansion and the unique games conjecture
- On Khot’s unique games conjecture
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- Subexponential Algorithms for Unique Games and Related Problems
- Making the Long Code Shorter
- Conditional Hardness for Approximate Coloring
- On the power of unique 2-prover 1-round games
- Probabilistic checking of proofs
- Interactive proofs and the hardness of approximating cliques
- A Parallel Repetition Theorem
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- On independent sets, 2-to-2 games, and Grassmann graphs
- Reducibility among Combinatorial Problems
- The Complexity of Public-Key Cryptography
- UG-hardness to NP-hardness by losing half
- Analysis of Boolean Functions
- Subsets of Cayley graphs that induce many edges
- Towards a proof of the 2-to-1 games conjecture?
- On non-optimally expanding sets in Grassmann graphs
- Candidate hard unique game
- Hypercontractivity, sum-of-squares proofs, and their applications
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games
- A Two Prover One Round Game with Strong Soundness
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
This page was built for publication: Pseudorandom sets in Grassmann graph have near-perfect expansion
