DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.39

Nearly Orthogonal Sets over Finite Fields

Authors: Dror Chawin and Ishay Haviv

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

For a field 𝔽 and integers d and k, a set of vectors of 𝔽^d is called k-nearly orthogonal if its members are non-self-orthogonal and every k+1 of them include an orthogonal pair. We prove that for every prime p there exists a positive constant δ = δ (p), such that for every field 𝔽 of characteristic p and for all integers k ≥ 2 and d ≥ k^{1/(p-1)}, there exists a k-nearly orthogonal set of at least d^{δ ⋅ k^{1/(p-1)} / log k} vectors of 𝔽^d. In particular, for the binary field we obtain a set of d^Ω(k/log k) vectors, and this is tight up to the log k term in the exponent. For comparison, the best known lower bound over the reals is d^Ω(log k / log log k)} (Alon and Szegedy, Graphs and Combin., 1999). The proof combines probabilistic and spectral arguments.

Cite as

Dror Chawin and Ishay Haviv. Nearly Orthogonal Sets over Finite Fields. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 39:1-39:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chawin_et_al:LIPIcs.SoCG.2024.39,
  author =	{Chawin, Dror and Haviv, Ishay},
  title =	{{Nearly Orthogonal Sets over Finite Fields}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{39:1--39:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.39},
  URN =		{urn:nbn:de:0030-drops-199848},
  doi =		{10.4230/LIPIcs.SoCG.2024.39},
  annote =	{Keywords: Nearly orthogonal sets, Finite fields}
}

Document

DOI: 10.4230/LIPIcs.STACS.2023.20

Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank

Authors: Dror Chawin and Ishay Haviv

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract

The orthogonality dimension of a graph G over ℝ is the smallest integer k for which one can assign a nonzero k-dimensional real vector to each vertex of G, such that every two adjacent vertices receive orthogonal vectors. We prove that for every sufficiently large integer k, it is NP-hard to decide whether the orthogonality dimension of a given graph over ℝ is at most k or at least 2^{(1-o(1))⋅k/2}. We further prove such hardness results for the orthogonality dimension over finite fields as well as for the closely related minrank parameter, which is motivated by the index coding problem in information theory. This in particular implies that it is NP-hard to approximate these graph quantities to within any constant factor. Previously, the hardness of approximation was known to hold either assuming certain variants of the Unique Games Conjecture or for approximation factors smaller than 3/2. The proofs involve the concept of line digraphs and bounds on their orthogonality dimension and on the minrank of their complement.

Cite as

Dror Chawin and Ishay Haviv. Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chawin_et_al:LIPIcs.STACS.2023.20,
  author =	{Chawin, Dror and Haviv, Ishay},
  title =	{{Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.20},
  URN =		{urn:nbn:de:0030-drops-176724},
  doi =		{10.4230/LIPIcs.STACS.2023.20},
  annote =	{Keywords: hardness of approximation, graph coloring, orthogonality dimension, minrank, index coding}
}

Search Results

Documents authored by Chawin, Dror

Nearly Orthogonal Sets over Finite Fields

Abstract

Cite as

Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank

Abstract

Cite as

Thanks for your feedback!

Could not send message