48 citations · 68 across the 25 of their papers we have counts for
4 papers · 1 filter
Kernelization for -Coloring
Yael Berkman, Ishay Haviv
For a fixed graph , the -Coloring problem asks whether a given graph admits an edge-preserving function from its vertex set to that of . A seminal theorem of Hell and Neše…
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…
A Near-Optimal Kernel for a Coloring Problem
Ishay Haviv, Dror Rabinovich
For a fixed integer , the -Coloring problem asks to decide if a given graph has a vertex coloring with colors such that no two adjacent vertices receive the same color. I…
Kernels for Storage Capacity and Dual Index Coding
Ishay Haviv
The storage capacity of a graph measures the maximum amount of information that can be stored across its vertices, such that the information at any vertex can be recovered from the…