6 papers
New Hardness Results for Low-Rank Matrix Completion
Dror Chawin, Ishay Haviv
The low-rank matrix completion problem asks whether a given real matrix with missing values can be completed so that the resulting matrix has low rank or is close to a low-rank mat…
Improved Approximation Algorithms for Index Coding
Dror Chawin, Ishay Haviv
The index coding problem is concerned with broadcasting encoded information to a collection of receivers in a way that enables each receiver to discover its required data based on…
Nearly Orthogonal Sets over Finite Fields
Dror Chawin, Ishay Haviv
For a field and integers and , a set of vectors of is called -nearly orthogonal if its members are non-self-orthogonal and every of them…
Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
Dror Chawin, Ishay Haviv
The orthogonality dimension of a graph over is the smallest integer for which one can assign a nonzero -dimensional real vector to each vertex of , such…
On the Subspace Choosability in Graphs
Dror Chawin, Ishay Haviv
A graph is said to be -subspace choosable over a field if for every assignment of -dimensional subspaces of some finite-dimensional vector space over $\mathb…
Lower Bounds on the Time/Memory Tradeoff of Function Inversion
Dror Chawin, Iftach Haitner, Noam Mazor
We study time/memory tradeoffs of function inversion: an algorithm, i.e., an inverter, equipped with an s-bit advice on a randomly chosen function and using or…