Approximating the orthogonality dimension of graphs and hypergraphs
From MaRDI portal
Publication:5870293
DOI10.4086/CJTCS.2022.002OpenAlexW4365130787MaRDI QIDQ5870293FDOQ5870293
Authors: Ishay Haviv 
Publication date: 6 January 2023
Published in: Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/cjtcs.2022.002
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
semidefinite programminghardness of approximationorthogonality dimensionKneser and Schrijver graphsorthogonal representations of hypergraphs
Cites Work
- Reducibility among combinatorial problems
- On the quantum chromatic number of a graph
- Forbidden Intersections
- Approximate graph coloring by semidefinite programming
- On the Shannon capacity of a graph
- Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
- Proof verification and the hardness of approximation problems
- Probabilistic checking of proofs
- Title not available (Why is that?)
- Kneser's conjecture, chromatic number, and homotopy
- On the hardness of approximating minimum vertex cover
- Title not available (Why is that?)
- Conditional Hardness for Approximate Coloring
- Title not available (Why is that?)
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Improving the performance guarantee for approximate graph coloring
- New approximation algorithms for graph coloring
- n-tuple colorings and associated graphs
- A Parallel Repetition Theorem
- The multichromatic numbers of some Kneser graphs
- New approximation guarantee for chromatic number
- Extremal problems concerning Kneser-graphs
- Orthogonal representations and connectivity of graphs
- The Complexity of Near-Optimal Graph Coloring
- Approximating coloring and maximum independent sets in 3-uniform hypergraphs
- Orthogonal representations over finite fields and the chromatic number of graphs
- Two-query PCP with subconstant error
- New hardness results for graph and hypergraph colorings
- Coloring -colorable graphs using relatively small palettes
- The hardness of 3-uniform hypergraph coloring
- Topological bounds on the dimension of orthogonal representations of graphs
- Title not available (Why is that?)
- Coloring bipartite hypergraphs
- Hardness of Approximate Hypergraph Coloring
- On the hardness of approximating the chromatic number
- The Minrank of Random Graphs
- On the Hardness of 4-Coloring a 3-Colorable Graph
- Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
- Title not available (Why is that?)
- Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
- Algebraic Approach to Promise Constraint Satisfaction
- On a Fractional Version of Haemers’ Bound
- Graphs and geometry
- The (generalized) orthogonality dimension of (generalized) kneser graphs: bounds and applications
- Topological bounds for graph representations over any field
- Round elimination in exact communication complexity
- Linear index coding via semidefinite programming
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
Cited In (4)
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)
