Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
From MaRDI portal
Publication:6071819
DOI10.1137/23m155760xzbMath1527.05060arXiv2301.00732OpenAlexW4388671588MaRDI QIDQ6071819
Publication date: 29 November 2023
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2301.00732
Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Complexity of computation (including implicit computational complexity) (03D15) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some properties of line digraphs
- Coloring graphs with locally few colors
- On the complexity of H-coloring
- On the arc-chromatic number of a digraph
- n-tuple colorings and associated graphs
- The Shannon capacity of a union
- Orthogonal representations and connectivity of graphs
- Arc colorings of digraphs
- Orthogonal representations over finite fields and the chromatic number of graphs
- Improved Hardness of Approximating Chromatic Number
- Optimal Index Codes With Near-Extreme Rates
- Coloring 3-Colorable Graphs with Less than n 1/5 Colors
- Conditional Hardness for Approximate Coloring
- On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors
- The Complexity of Near-Optimal Graph Coloring
- On the Shannon capacity of a graph
- On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
- Reducibility among Combinatorial Problems
- Algebraic Approach to Promise Constraint Satisfaction
- Improved hardness for H-colourings of G-colourable graphs
- Graphs and Geometry
- Index Coding With Side Information
- On the Hardness of Approximating the Network Coding Capacity
- New hardness results for graph and hypergraph colorings
- Linear Index Coding via Semidefinite Programming
- On chromatic number of graphs and set-systems
- On the hardness of approximating the chromatic number
- Local orthogonality dimension
