scientific article; zbMATH DE number 7639160
From MaRDI portal
Publication:5870293
DOI10.4086/cjtcs.2022.002OpenAlexW4365130787MaRDI QIDQ5870293
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
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
semidefinite programminghardness of approximationorthogonality dimensionKneser and Schrijver graphsorthogonal representations of hypergraphs
Related Items
Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank, Local orthogonality dimension
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Kneser's conjecture, chromatic number, and homotopy
- On the hardness of approximating minimum vertex cover
- On the quantum chromatic number of a graph
- Extremal problems concerning Kneser-graphs
- n-tuple colorings and associated graphs
- The multichromatic numbers of some Kneser graphs
- Orthogonal representations and connectivity of graphs
- Topological bounds on the dimension of orthogonal representations of graphs
- The hardness of 3-uniform hypergraph coloring
- Orthogonal representations over finite fields and the chromatic number of graphs
- Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
- New approximation guarantee for chromatic number
- Hardness of Approximate Hypergraph Coloring
- Proof verification and the hardness of approximation problems
- Coloring 3-Colorable Graphs with Less than n 1/5 Colors
- Conditional Hardness for Approximate Coloring
- Two-query PCP with subconstant error
- Forbidden Intersections
- Improving the performance guarantee for approximate graph coloring
- Probabilistic checking of proofs
- Approximate graph coloring by semidefinite programming
- The Complexity of Near-Optimal Graph Coloring
- On the Shannon capacity of a graph
- New approximation algorithms for graph coloring
- A Parallel Repetition Theorem
- The Minrank of Random Graphs
- Coloring bipartite hypergraphs
- On the Hardness of 4-Coloring a 3-Colorable Graph
- Coloring -colorable graphs using relatively small palettes
- Reducibility among Combinatorial Problems
- Algebraic Approach to Promise Constraint Satisfaction
- Improved hardness for H-colourings of G-colourable graphs
- Topological Bounds for Graph Representations over Any Field
- On a Fractional Version of Haemers’ Bound
- Graphs and Geometry
- Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
- New hardness results for graph and hypergraph colorings
- Linear Index Coding via Semidefinite Programming
- On the hardness of approximating the chromatic number
- The (generalized) orthogonality dimension of (generalized) kneser graphs: bounds and applications
