Showing cs.CCShow all
3 papers · 1 filter
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.CC2023
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…
cs.CC2021
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…