On independent sets, 2-to-2 games, and Grassmann graphs
From MaRDI portal
(Redirected from Publication:4978004)
Games on graphs (graph-theoretic aspects) (05C57) Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
Recommendations
- Towards a proof of the 2-to-1 games conjecture?
- On the proof of the 2-to-2 games conjecture
- On the complexity of approximating the independent set problem
- Inapproximability of vertex cover and independent set in bounded degree graphs
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(36)- Boolean degree 1 functions on some classical association schemes
- On non-optimally expanding sets in Grassmann graphs
- Upper and lower degree-constrained graph orientation with minimum penalty
- Log-Sobolev inequality for the multislice, with applications
- New tools and connections for exponential-time approximation
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- Boolean function analysis on high-dimensional expanders
- On the proof of the 2-to-2 games conjecture
- Small-set expansion in shortcode graph and the 2-to-2 conjecture
- A log-Sobolev inequality for the multislice, with applications
- UG-hardness to NP-hardness by losing half
- Towards a proof of the 2-to-1 games conjecture?
- Approximating power node-deletion problems
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- scientific article; zbMATH DE number 7716602 (Why is no real title available?)
- Mathematics of computation through the lens of linear equations and lattices
- Approximate graph colouring and the hollow shadow
- The power of unentangled quantum proofs with non-negative amplitudes
- Boolean function analysis on high-dimensional expanders
- Conditional dichotomy of Boolean ordered promise CSPs
- Approximating power node-deletion problems
- d-to-1 hardness of coloring 3-colorable graphs with o(1) colors
- 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
- On equivalence of parameterized inapproximability of k-median, k-max-coverage, and 2-CSP
- Approximate graph coloring and the crystal with a hollow shadow
- Improved optimal testing results from global hypercontractivity
- On rich 2-to-1 games
- Conditional dichotomy of Boolean ordered promise CSPs
- On equivalence of parameterized inapproximability of \(k\)-median, \(k\)-max-coverage, and 2-CSP
- Undefinability of approximation of 2-to-2 games
- Garland's technique for posets and high-dimensional Grassmannian expanders
- An 11/6-approximation algorithm for vertex cover on string graphs
- A randomized rounding approach for DAG edge deletion
This page was built for publication: On independent sets, 2-to-2 games, and Grassmann graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978004)
