10 papers
Fair Allocation under Conflict Constraints via Strong Colorability
Ishay Haviv
In the fair allocation problem under conflict constraints, the goal is to partition the vertices of a graph among agents in a fair manner, such that no two adjacent vertices are as…
Setwise Distinguishable Permutations
Ishay Haviv
A family of permutations of is called setwise distinguishable if for every permutation in the family there exists a subset of whose image under this permutation differs…
Kernelization Bounds for Constrained Coloring
Ishay Haviv
We study the kernel complexity of constraint satisfaction problems over a finite domain, parameterized by the number of variables, whose constraint language consists of two relatio…
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Å¡…
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…