Pseudorandom sets in Grassmann graph have near-perfect expansion
From MaRDI portal
Publication:6101019
Cites work
- \(\mathcal{NP}\)-hardness of approximately solving linear equations over reals
- A Parallel Repetition Theorem
- A threshold of ln n for approximating set cover
- A Two Prover One Round Game with Strong Soundness
- Analysis of Boolean Functions
- Applications of ANOVA type decompositions for comparisons of conditional variance statistics including jackknife estimates
- Approximation algorithms for NP-hard problems.
- Candidate hard unique game
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Conditional Hardness for Approximate Coloring
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Graph expansion and the unique games conjecture
- Hardness of approximation
- How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games
- scientific article; zbMATH DE number 5971212 (Why is no real title available?)
- scientific article; zbMATH DE number 5485476 (Why is no real title available?)
- scientific article; zbMATH DE number 5485509 (Why is no real title available?)
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- Hypercontractivity, sum-of-squares proofs, and their applications
- Improved inapproximability results for maximum k-colorable subgraph
- Inapproximability of combinatorial optimization problems
- Interactive proofs and the hardness of approximating cliques
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Making the Long Code Shorter
- On independent sets, 2-to-2 games, and Grassmann graphs
- On Khot’s unique games conjecture
- On non-optimally expanding sets in Grassmann graphs
- On the efficient approximability of constraint satisfaction problems
- On the hardness of approximating minimum vertex cover
- On the hardness of approximating Multicut and Sparsest-Cut
- On the power of unique 2-prover 1-round games
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Reducibility among combinatorial problems
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- SDP gaps and UGC-hardness for max-cut-gain
- Small-set expansion in shortcode graph and the 2-to-2 conjecture
- Some optimal inapproximability results
- Subexponential algorithms for unique games and related problems
- Subsets of Cayley graphs that induce many edges
- The Complexity of Public-Key Cryptography
- The jackknife estimate of variance
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
- Towards a proof of the 2-to-1 games conjecture?
- Towards a proof of the Fourier-entropy conjecture?
- UG-hardness to NP-hardness by losing half
- Unique games on expanding constraint graphs are easy (extended abstract)
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(20)- Approximating power node-deletion problems
- 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
- Approximate graph colouring and the hollow shadow
- The power of unentangled quantum proofs with non-negative amplitudes
- Approximation algorithms for partial vertex covers in trees
- Sparse juntas on the biased hypercube
- Improved covering results for conjugacy classes of symmetric groups via hypercontractivity
- Towards a proof of the 2-to-1 games conjecture
- On independent sets, 2-to-2 games and Grassmann graphs
- Small-set expansion in the Johnson graph
- Solving unique games over globally hypercontractive graphs
- An invariance principle for the multi-slice, with applications
- Sphere valued noise stability and quantum max-cut hardness
- Algebraic approach to approximation
- Agreement tests on graphs and hypergraphs
- Undefinability of approximation of 2-to-2 games
This page was built for publication: Pseudorandom sets in Grassmann graph have near-perfect expansion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6101019)
