The chromatic number of an nn-vertex graph is NP-hard to approximate within a factor of n1−εn^{1-\varepsilon} for every fixed ε>0\varepsilon>0 (Zuckerman), yet for its closest algebraic analogues — the orthogonality dimension ξ‾F(G)\overline{\xi}_{\mathbb{F}}(G) over the reals and over finite fields, and the minrank minrk⁡F(G)\operatorname{minrk}_{\mathbb{F}}(G), which exactly characterizes the optimal length of linear index codes — the strongest unconditional hardness of approximation (Chawin–Haviv, 2023) covers only constant-factor gaps: for every finite field it is NP-hard to decide ξ‾F(G)≤k\overline{\xi}_{\mathbb{F}}(G)\le k versus ξ‾F(G)≥2(1−o(1))k/2\overline{\xi}_{\mathbb{F}}(G)\ge 2^{(1-o(1))k/2}, and likewise for minrank. This problem asks whether near-optimal, vertex-count-dependent inapproximability extends to these algebraic parameters, i.e., whether approximating them within n1−εn^{1-\varepsilon} is NP-hard for some (ultimately every) fixed ε>0\varepsilon>0; and, as the directly linked companion facet, whether the general (nonlinear) index coding problem over a constant-size alphabet is NP-hard at all — no NP-hardness of any kind is currently known for it. Both facets remain open as of August 2026: the known reduction route through line digraphs provably loses a quadratic factor and is capped by subspace-Sperner barrier results, while on the algorithmic side O(n/log⁡2n)O(n/\log^2 n)-approximation algorithms already exist.

Background

The chromatic number χ(G)\chi(G) of a graph GG — the minimum number of colors needed to color the vertices so that adjacent vertices receive distinct colors — is a canonical NP-hard quantity to compute and to approximate. Research has therefore focused on its gap (promise) problems: for integers k1<k2k_1<k_2, decide whether a given graph satisfies χ(G)≤k1\chi(G)\le k_1 or χ(G)≥k2\chi(G)\ge k_2; NP-hardness of such a gap problem implies NP-hardness of approximating χ\chi within any factor smaller than k2/k1k_2/k_1. The strongest known NP-hard gap is due to Wrochna and Živný: for every k≥4k\ge 4 it is NP-hard to decide whether χ(G)≤k\chi(G)\le k or χ(G)≥b(k)\chi(G)\ge b(k), where b(k)=(k⌊k/2⌋)b(k)=\binom{k}{\lfloor k/2\rfloor}. In a complementary direction, Zuckerman proved that for every ε>0\varepsilon>0 it is NP-hard to approximate χ(G)\chi(G) on nn-vertex graphs within a factor of n1−εn^{1-\varepsilon}, which is near-optimal against the trivial factor-nn upper bound.

This problem concerns two algebraic analogues of the chromatic number. The orthogonality dimension ξF(G)\xi_{\mathbb{F}}(G) of a graph GG over a field F\mathbb{F}, a notion studied since Lovász's work on the Shannon capacity of a graph (the zero-error capacity of a noisy communication channel, for which Haemers introduced minrank as an upper bound), is the smallest integer kk for which every vertex vv of GG can be assigned a nonzero vector uv∈Fku_v\in\mathbb{F}^k with ⟨uv,uv⟩≠0\langle u_v,u_v\rangle\ne 0 (non-self-orthogonal under the standard bilinear inner product) such that ⟨uv,uw⟩=0\langle u_v,u_w\rangle=0 whenever vv and ww are adjacent. Following Chawin and Haviv, we write ξ‾F(G)=ξF(G‾)\overline{\xi}_{\mathbb{F}}(G)=\xi_{\mathbb{F}}(\overline{G}) for the complement graph. For every field F\mathbb{F} one has ξF(G)≤χ(G)\xi_{\mathbb{F}}(G)\le\chi(G), and if F\mathbb{F} is R\mathbb{R} or a fixed finite field one additionally has ξF(G)≥Ω(log⁡χ(G))\xi_{\mathbb{F}}(G)\ge\Omega(\log\chi(G)); both bounds are tight in the worst case, and over R\mathbb{R} the lower bound holds with the explicit constant log⁡3χ(G)≤ξR(G)\log_3\chi(G)\le\xi_{\mathbb{R}}(G). The minrank minrk⁡F(G)\operatorname{minrk}_{\mathbb{F}}(G) is the smallest rank of a matrix MM over F\mathbb{F} that represents GG, meaning Mi,i≠0M_{i,i}\ne 0 for all ii and Mi,j=0M_{i,j}=0 for distinct non-adjacent vertices i,ji,j; it satisfies minrk⁡F(G)≤ξ‾F(G)\operatorname{minrk}_{\mathbb{F}}(G)\le\overline{\xi}_{\mathbb{F}}(G). Computational interest in these parameters dates back to Lovász, Saks, and Schrijver, who noted in 1989 that determining the orthogonality dimension seems difficult.

Both parameters are motivated by the index coding problem of Bar-Yossef, Birk, Jayram, and Kol: a sender holds nn messages and must broadcast to nn receivers, where receiver ii wants message xix_i and knows the messages of its neighbors in a given side-information graph GG; an index code over an alphabet Σ\Sigma of length kk is an encoding function E:Σn→ΣkE:\Sigma^n\to\Sigma^k such that each receiver can recover its own message from the broadcast together with its side information. When the encoding is required to be linear over a field F\mathbb{F}, the optimal length equals minrk⁡F(G)\operatorname{minrk}_{\mathbb{F}}(G); the general (nonlinear) problem allows arbitrary encoding functions and can be strictly more powerful.

On the computational side, Peeters proved in 1996 that for every field it is NP-hard to decide whether the orthogonality dimension or the minrank of a given graph is at most 33, and Dau, Skachek, and Chee proved NP-completeness of deciding minrank 22 for digraphs over F2\mathbb{F}_2; Golovnev and Haviv extended hardness for the real orthogonality dimension to approximation factors below 3/23/2. Under variants of the Unique Games Conjecture (a standard complexity assumption about the hardness of certain constraint satisfaction problems), Langberg and Sprintson showed hardness of arbitrary constant-factor gap problems for minrank and, in certain settings, for the general index coding problem; Chawin and Haviv (2023) established the first unconditional constant-factor NP-hardness: for every finite field F\mathbb{F} (and analogously over R\mathbb{R}), there exists f(k)=2(1−o(1))k/2f(k)=2^{(1-o(1))k/2} such that for all large kk it is NP-hard to decide ξ‾F(G)≤k\overline{\xi}_{\mathbb{F}}(G)\le k versus ξ‾F(G)≥f(k)\overline{\xi}_{\mathbb{F}}(G)\ge f(k), and the same holds for minrk⁡F(G)\operatorname{minrk}_{\mathbb{F}}(G) over finite fields. Their technique reduces chromatic gap instances to the underlying graphs of line digraphs (the line digraph δG\delta G has as vertices the ordered pairs of adjacent vertices of GG, with an edge from (x,y)(x,y) to (y,z)(y,z)); if HH denotes the underlying graph of δG\delta G, the algebraic parameters are quadratically related to the chromatic number on these graphs, so the chromatic gap b(k)b(k) transfers with a square-root loss: ξF(H)≥log⁡∣F∣χ(G)\xi_{\mathbb{F}}(H)\ge\sqrt{\log_{|\mathbb{F}|}\chi(G)} and minrk⁡F(H‾)≥12log⁡∣F∣χ(G)\operatorname{minrk}_{\mathbb{F}}(\overline{H})\ge\tfrac12\sqrt{\log_{|\mathbb{F}|}\chi(G)}. The paper also proves two barriers: the clique number of the subspace graph S(F,n)S(\mathbb{F},n), whose vertices are the subspaces of Fn\mathbb{F}^n with two distinct subspaces adjacent when each of them includes a non-self-orthogonal vector orthogonal to the entire other subspace, equals (n⌊n/2⌋)\binom{n}{\lfloor n/2\rfloor} by a subspace analogue of Sperner's theorem due to Kalai, capping that route; and over the reals the analogous graph S′(R,n)S'(\mathbb{R},n), whose vertices are the pairs of subspaces of Rn\mathbb{R}^n, has infinite chromatic number for n≥3n\ge 3, since there exist graphs with minrk⁡R≤3\operatorname{minrk}_{\mathbb{R}}\le 3 and arbitrarily large chromatic number, which blocks the real-minrank route entirely. The same paper relates the general (nonlinear) index coding question to a purely chromatic one: its Theorem 4.7 shows that NP-hardness of deciding, for some integer kk, whether χ(G)≤b(k)\chi(G)\le b(k) or χ(G)>2∣Σ∣k\chi(G)>2^{|\Sigma|^{k}} for an alphabet Σ\Sigma, where b(k)=(k⌊k/2⌋)b(k)=\binom{k}{\lfloor k/2\rfloor}, would imply NP-hardness of general index coding over Σ\Sigma — a single-exponential-versus-super-exponential chromatic gap that goes beyond the strongest known gap.

On the algorithmic side, Chawin and Haviv (2024) later gave polynomial-time algorithms approximating the index coding rate of nn-vertex graphs within O(n/log⁡2n)O(n/\log^2 n) (digraphs within O(n/log⁡n)O(n/\log n)), via a framework that also covers the minrank parameter and related quantities. Since n/log⁡2n=n1−o(1)n/\log^2 n=n^{1-o(1)}, the approximability landscape for these parameters currently sits between constant-factor NP-hardness and n1−o(1)n^{1-o(1)}-approximability, in sharp contrast with the chromatic number, where Zuckerman's n1−εn^{1-\varepsilon} hardness is nearly tight. Whether the near-optimal hardness extends to the algebraic parameters — and whether the general index coding problem is NP-hard at all — is the subject of this problem.

Problem Statement

The problem consists of two linked facets, both explicitly posed by Chawin and Haviv (2023), sharing one scientific objective: locating the worst-case hardness of the algebraic analogues of graph coloring — and of the index coding problem they govern — relative to the chromatic-number benchmark.

Facet 1 (near-optimal inapproximability of the algebraic parameters). Determine whether, for some fixed ε>0\varepsilon>0 (and ultimately for every ε>0\varepsilon>0), it is NP-hard to approximate ξ‾R(G)\overline{\xi}_{\mathbb{R}}(G), or ξ‾F(G)\overline{\xi}_{\mathbb{F}}(G) over a fixed finite field F\mathbb{F}, or minrk⁡F(G)\operatorname{minrk}_{\mathbb{F}}(G) over a fixed finite field, on nn-vertex graphs to within a factor of n1−εn^{1-\varepsilon}. In gap form: do there exist k1(n)<k2(n)k_1(n)<k_2(n) with k2(n)/k1(n)≥n1−εk_2(n)/k_1(n)\ge n^{1-\varepsilon} such that deciding ψ(G)≤k1(n)\psi(G)\le k_1(n) versus ψ(G)≥k2(n)\psi(G)\ge k_2(n) is NP-hard for one of these parameters ψ\psi? An affirmative answer for any one of the parameter settings (with explicit ε\varepsilon) resolves the qualitative question; matching Zuckerman's every-ε\varepsilon statement is the quantitative target. A refutation for a parameter and ε\varepsilon takes the form of a polynomial-time n1−εn^{1-\varepsilon}-approximation algorithm for it — note that O(n/log⁡2n)O(n/\log^2 n) algorithms already exist, so a refutation requires beating that scale at a fixed power of nn.

Facet 2 (NP-hardness of general index coding). Determine whether the general (nonlinear) index coding problem over a constant-size alphabet is NP-hard: does there exist a fixed alphabet Σ\Sigma with ∣Σ∣≥2|\Sigma|\ge 2 and integers k1<k2k_1<k_2 such that deciding whether a given instance with symmetric side information admits an index code over Σ\Sigma of length at most k1k_1, versus requires length at least k2k_2, is NP-hard? No NP-hardness result of any kind is currently known.

References

  1. D. Chawin and I. Haviv, 'Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank', SIAM Journal on Discrete Mathematics 37(4):2670–2688, 2023. DOI: 10.1137/23M155760X; arXiv:2301.00732, https://arxiv.org/abs/2301.00732
  2. D. Zuckerman, 'Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number', Theory of Computing 3(6):103–128, 2007. DOI: 10.4086/toc.2007.v003a006, https://theoryofcomputing.org/articles/v003a006
  3. M. Wrochna and S. Živný, 'Improved hardness for H-colourings of G-colourable graphs', Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pp. 1426–1435. DOI: 10.1137/1.9781611975994.86, https://doi.org/10.1137/1.9781611975994.86
  4. R. Peeters, 'Orthogonal representations over finite fields and the chromatic number of graphs', Combinatorica 16(3):417–431, 1996. DOI: 10.1007/BF01261326, https://doi.org/10.1007/BF01261326
  5. M. Langberg and A. Sprintson, 'On the Hardness of Approximating the Network Coding Capacity', IEEE Transactions on Information Theory 57(2):1008–1014, 2011. DOI: 10.1109/TIT.2010.2094910, https://doi.org/10.1109/TIT.2010.2094910
  6. Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol, 'Index Coding With Side Information', IEEE Transactions on Information Theory 57(3):1479–1494, 2011. DOI: 10.1109/TIT.2010.2103753, https://doi.org/10.1109/TIT.2010.2103753
  7. W. H. Haemers, 'On Some Problems of Lovász Concerning the Shannon Capacity of a Graph', IEEE Transactions on Information Theory 25(2):231–232, 1979. DOI: 10.1109/TIT.1979.1056027, https://doi.org/10.1109/TIT.1979.1056027
  8. L. Lovász, 'On the Shannon capacity of a graph', IEEE Transactions on Information Theory 25(1):1–7, 1979. DOI: 10.1109/TIT.1979.1055985, https://doi.org/10.1109/TIT.1979.1055985
  9. L. Lovász, M. Saks, and A. Schrijver, 'Orthogonal representations and connectivity of graphs', Linear Algebra and its Applications 114–115:439–454, 1989. DOI: 10.1016/0024-3795(89)90475-8, https://doi.org/10.1016/0024-3795(89)90475-8
  10. G. Kalai, 'Analogues for Sperner and Erdős–Ko–Rado Theorems For Subspaces of Linear Spaces', in P. Hammer (ed.), Combinatorics 79, Annals of Discrete Mathematics, vol. 9, p. 135, 1980. DOI: 10.1016/S0167-5060(08)70049-9, https://doi.org/10.1016/S0167-5060(08)70049-9
  11. A. Golovnev and I. Haviv, 'The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications', Theory of Computing 18(22):1–22, 2022. DOI: 10.4086/toc.2022.v018a022, https://theoryofcomputing.org/articles/v018a022
  12. S. H. Dau, V. Skachek, and Y. M. Chee, 'Optimal Index Codes with Near-Extreme Rates', IEEE Transactions on Information Theory 60(3):1515–1527, 2014. DOI: 10.1109/TIT.2013.2295331, https://doi.org/10.1109/TIT.2013.2295331; arXiv:1202.1150, https://arxiv.org/abs/1202.1150
  13. D. Chawin and I. Haviv, 'Hardness of Linear Index Coding on Perturbed Instances', IEEE Transactions on Information Theory 70(2):1388–1396, 2024. DOI: 10.1109/TIT.2023.3347296, https://doi.org/10.1109/TIT.2023.3347296
  14. D. Chawin and I. Haviv, 'Improved Approximation Algorithms for Index Coding', IEEE Transactions on Information Theory 70(8):8266–8275, 2024. DOI: 10.1109/TIT.2024.3446000; arXiv:2408.08382, https://arxiv.org/abs/2408.08382
  15. D. Chawin and I. Haviv, 'New Hardness Results for Low-Rank Matrix Completion', 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), LIPIcs vol. 345, article 37, pp. 37:1–37:18, 2025. DOI: 10.4230/LIPICS.MFCS.2025.37, https://doi.org/10.4230/LIPICS.MFCS.2025.37; arXiv:2506.18440, https://arxiv.org/abs/2506.18440
  16. I. Haviv and D. Rabinovich, 'Kernelization for Orthogonality Dimension', Journal of Computer and System Sciences, vol. 157, article 103757, 2026. DOI: 10.1016/j.jcss.2026.103757, https://doi.org/10.1016/j.jcss.2026.103757; arXiv:2408.08380, https://arxiv.org/abs/2408.08380
  17. I. Haviv, 'Kernels for storage capacity and dual index coding', Journal of Combinatorial Theory, Series A 216:106059, 2025. DOI: 10.1016/j.jcta.2025.106059, https://doi.org/10.1016/j.jcta.2025.106059
  18. A. Khalesi and P. Elia, 'Hyper-Minrank: A Unified Hypergraph Characterization of Multi-Sender Index Coding', arXiv:2512.13615, 2025, https://arxiv.org/abs/2512.13615