Dror Rabinovich

dblp:385/7292 · DBLP profile ↗
← Back
3ranked-venue papers
0as first author
3since 2021 · last 2026
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 3 since 2021
YearPublicationVenuePosition
2026 Kernelization for orthogonality dimension
Ishay Haviv, Dror Rabinovich
J. Comput. Syst. Sci.2
2025 A near-optimal kernel for a coloring problem
Ishay Haviv, Dror Rabinovich
Discret. Appl. Math.2
2024 Kernelization for Orthogonality Dimension
abstract
The orthogonality dimension of a graph over $\mathbb{R}$ is the smallest integer $d$ for which one can assign to every vertex a nonzero vector in $\mathbb{R}^d$ such that every two adjacent vertices receive orthogonal vectors. For an integer $d$, the $d$-Ortho-Dim$_\mathbb{R}$ problem asks to decide whether the orthogonality dimension of a given graph over $\mathbb{R}$ is at most $d$. We prove that for every integer $d \geq 3$, the $d$-Ortho-Dim$_\mathbb{R}$ problem parameterized by the vertex cover number $k$ admits a kernel with $O(k^{d-1})$ vertices and bit-size $O(k^{d-1} \cdot \log k)$. We complement this result by a nearly matching lower bound, showing that for any $\varepsilon > 0$, the problem admits no kernel of bit-size $O(k^{d-1-\varepsilon})$ unless $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. We further study the kernelizability of orthogonality dimension problems in additional settings, including over general fields and under various structural parameterizations.
Ishay Haviv, Dror Rabinovich
IPEC2