Approximating the orthogonality dimension of graphs and hypergraphs
From MaRDI portal
Recommendations
- Approximating the orthogonality dimension of graphs and hypergraphs
- The (generalized) orthogonality dimension of (generalized) Kneser graphs: bounds and applications
- Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
- The (generalized) orthogonality dimension of (generalized) kneser graphs: bounds and applications
- Local orthogonality dimension
Cites work
- A Parallel Repetition Theorem
- Algebraic Approach to Promise Constraint Satisfaction
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Approximate graph coloring by semidefinite programming
- Approximating coloring and maximum independent sets in 3-uniform hypergraphs
- Coloring -colorable graphs using relatively small palettes
- Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
- Coloring bipartite hypergraphs
- Conditional Hardness for Approximate Coloring
- Extremal problems concerning Kneser-graphs
- Forbidden Intersections
- Graphs and geometry
- Hardness of Approximate Hypergraph Coloring
- scientific article; zbMATH DE number 1002208 (Why is no real title available?)
- scientific article; zbMATH DE number 3672329 (Why is no real title available?)
- scientific article; zbMATH DE number 3745081 (Why is no real title available?)
- scientific article; zbMATH DE number 3503283 (Why is no real title available?)
- scientific article; zbMATH DE number 3251317 (Why is no real title available?)
- Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
- Improving the performance guarantee for approximate graph coloring
- Kneser's conjecture, chromatic number, and homotopy
- Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
- Linear index coding via semidefinite programming
- n-tuple colorings and associated graphs
- New approximation algorithms for graph coloring
- New approximation guarantee for chromatic number
- New hardness results for graph and hypergraph colorings
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
- On a Fractional Version of Haemers’ Bound
- On the Hardness of 4-Coloring a 3-Colorable Graph
- On the hardness of approximating minimum vertex cover
- On the hardness of approximating the chromatic number
- On the quantum chromatic number of a graph
- On the Shannon capacity of a graph
- Orthogonal representations and connectivity of graphs
- Orthogonal representations over finite fields and the chromatic number of graphs
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Reducibility among combinatorial problems
- Round elimination in exact communication complexity
- The (generalized) orthogonality dimension of (generalized) kneser graphs: bounds and applications
- The Complexity of Near-Optimal Graph Coloring
- The hardness of 3-uniform hypergraph coloring
- The Minrank of Random Graphs
- The multichromatic numbers of some Kneser graphs
- Topological bounds for graph representations over any field
- Topological bounds on the dimension of orthogonal representations of graphs
- Two-query PCP with subconstant error
Cited in
(9)- A correction: Orthogonal representations and connectivity of graphs
- The (generalized) orthogonality dimension of (generalized) Kneser graphs: bounds and applications
- Approximating the orthogonality dimension of graphs and hypergraphs
- Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
- Local orthogonality dimension
- The (generalized) orthogonality dimension of (generalized) kneser graphs: bounds and applications
- Kernelization for orthogonality dimension
- Kernelization for orthogonality dimension
- New hardness results for low-rank matrix completion
This page was built for publication: Approximating the orthogonality dimension of graphs and hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5870293)
