48 citations · 68 across the 25 of their papers we have counts for
43 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š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…
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…
Kernelization for Orthogonality Dimension
Ishay Haviv, Dror Rabinovich
The orthogonality dimension of a graph over is the smallest integer for which one can assign to every vertex a nonzero vector in such that every two…
Testing Intersectingness of Uniform Families
Ishay Haviv, Michal Parnas
A set family is called intersecting if every two members of intersect, and it is called uniform if all members of share a common size. A uniform fa…
Larger Nearly Orthogonal Sets over Finite Fields
Ishay Haviv, Sam Mattheus, Aleksa Milojević +1
For a field and integers and , a set is called -nearly orthogonal if its members are non-self-orthogonal and every ve…
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…
The Chromatic Number of Kneser Hypergraphs via Consensus Division
Ishay Haviv
We show that the Consensus Division theorem implies lower bounds on the chromatic number of Kneser hypergraphs, offering a novel proof for a result of Alon, Frankl, and Lovász (Tra…
On Finding Constrained Independent Sets in Cycles
Ishay Haviv
A subset of is called stable if it forms an independent set in the cycle on the vertex set . In 1978, Schrijver proved via a topological argument that…
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…
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
Ishay Haviv
The Kneser graph is defined for integers and with as the graph whose vertices are all the -subsets of where two such sets are…
The Binary Rank of Circulant Block Matrices
Ishay Haviv, Michal Parnas
The binary rank of a matrix is the smallest size of a partition of its ones into monochromatic combinatorial rectangles. A matrix is called $(k_1, \ldots, k_m ; n_1, \ldo…
A Fixed-Parameter Algorithm for the Kneser Problem
Ishay Haviv
The Kneser graph is defined for integers and with as the graph whose vertices are all the -subsets of where two such sets are adj…
On the Binary and Boolean Rank of Regular Matrices
Ishay Haviv, Michal Parnas
A matrix is said to be regular if all of its rows and columns have the same number of ones. We prove that for infinitely many integers , there exists a square regular $0,1…
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…
Local Orthogonality Dimension
Inon Attias, Ishay Haviv
An orthogonal representation of a graph over a field is an assignment of a vector to every vertex of , such that $\langle u_v,u_v \ra…
Upper Bounds on the Boolean Rank of Kronecker Products
Ishay Haviv, Michal Parnas
The Boolean rank of a -matrix , denoted , is the smallest number of monochromatic combinatorial rectangles needed to cover the -entries of . In 1988,…
The Complexity of Finding Fair Independent Sets in Cycles
Ishay Haviv
Let be a cycle graph and let be a partition of its vertex set into sets. An independent set of is said to fairly represent the partition if $|S \ca…
Minimizing the alphabet size of erasure codes with restricted decoding sets
Mira Gonen, Ishay Haviv, Michael Langberg +1
A Maximum Distance Separable code over an alphabet is defined via an encoding function that allows to retrieve a message from the codeword $…