3 papers
cs.CC2025
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…
cs.DS2024
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…
cs.CG2024
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…