IHIshay Haviv

Ishay Haviv

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Ishay Haviv has a total of 39 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    The Chromatic Number of Kneser Hypergraphs via Consensus Division

    by 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 and for its generalization by Kříž. Our approach is applied to study the computational complexity of the total search problem Kneser p , which given a succinct representation of a coloring of a p -uniform Kneser hypergraph with fewer colors than its chromatic number asks to find a monochromatic hyperedge. We prove that for every prime p , the Kneser p problem with an extended access to the input coloring is efficiently reducible to a quite weak approximation of the Consensus Division problem with p shares. In particular, for p =2, the problem is efficiently reducible to any non-trivial approximation of the Consensus Halving problem on normalized monotone functions. We further show that for every prime p , the Kneser p problem lies in the complexity class PPA -p . As an application, we establish limitations on the complexity of the Kneser p problem, restricted to colorings with a bounded number of colors.


  • Improved Approximation Algorithms for Index Coding

    by 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 its side information, which comprises the data required by some of the others. Given the side information map, represented by a graph in the symmetric case and by a digraph otherwise, the goal is to devise a coding scheme of minimum broadcast length. We present a general method for developing efficient algorithms for approximating the index coding rate for prescribed families of instances. As applications, we obtain polynomial-time algorithms that approximate the index coding rate of graphs and digraphs on n vertices to within factors of $O(n/\log ^{2} n)$ and $O(n/\log n)$ respectively. This improves on the approximation factors of $O(n/\log n)$ for graphs and $O(n \cdot \log \log n/\log n)$ for digraphs achieved by Blasiak, Kleinberg, and Lubetzky. For the family of quasi-line graphs, we exhibit a polynomial-time algorithm that approximates the index coding rate to within a factor of 2. This improves on the approximation factor of $O(n^{2/3})$ achieved by Arbabjolfaei and Kim for graphs on n vertices taken from certain sub-families of quasi-line graphs. Our approach is applicable for approximating a variety of additional graph and digraph quantities to within the same approximation factors. Specifically, it captures every graph quantity sandwiched between the independence number and the clique cover number and every digraph quantity sandwiched between the maximum size of an acyclic induced sub-digraph and the directed clique cover number.


  • Fixed-Parameter Algorithms for the Kneser and Schrijver Problems

    by Ishay Haviv

    The Kneser graph [Formula: see text] is defined for integers [Formula: see text] and [Formula: see text] with [Formula: see text] as the graph whose vertices are all the [Formula: see text]-subsets of [Formula: see text] where two such sets are adjacent if they are disjoint. The Schrijver graph [Formula: see text] is defined as the subgraph of [Formula: see text] induced by the collection of all [Formula: see text]-subsets of [Formula: see text] that do not include two consecutive elements modulo [Formula: see text]. It is known that the chromatic number of both [Formula: see text] and [Formula: see text] is [Formula: see text]. In the computational Kneser and Schrijver problems, we are given access to a coloring with [Formula: see text] colors of the vertices of [Formula: see text] and [Formula: see text], respectively, and the goal is to find a monochromatic edge. We prove that the problems admit randomized algorithms with running time [Formula: see text], hence they are fixed-parameter tractable with respect to the parameter [Formula: see text]. The analysis involves structural results on intersecting families and on induced subgraphs of Kneser and Schrijver graphs. We also study the Agreeable-Set problem of assigning a small subset of a set of [Formula: see text] items to a group of [Formula: see text] agents, so that all agents value the subset at least as much as its complement. As an application of our algorithm for the Kneser problem, we obtain a randomized polynomial-time algorithm for the Agreeable-Set problem for instances with [Formula: see text]. We further show that the Agreeable-Set problem is at least as hard as a variant of the Kneser problem with extended access to the input coloring.


  • Minimizing the Alphabet Size in Codes With Restricted Error Sets

    by Mira Gonen, Ishay Haviv, Michael Langberg, Alex Sprintson

    This paper focuses on the study of the minimum possible alphabet size of codes in a generalized setting where the coding scheme is required to handle a pre-specified set of erasure or error patterns, naturally represented by a hypergraph. The need for such codes arises in many settings of practical interest, including wireless communication and flash memory systems. In many such settings, a smaller field size is achievable than that offered by MDS and other standard codes. We establish a connection between the minimum alphabet size of codes in this generalized setting and the combinatorial properties of the hypergraph that represents the pre-specified collection of erasure or error patterns. We also establish connections between error and erasure correcting codes in our generalized setting. Finally, we consider a variation of the problem that allows a small probability of decoding error and relate it to an approximate version of hypergraph coloring.

  • Hardness of Linear Index Coding on Perturbed Instances

    by Dror Chawin, Ishay Haviv

    The index coding problem is concerned with the amount of information that a sender has to transmit to multiple receivers in a way that enables each of them to retrieve its requested data relying on prior side information. For linear index coding, the problem is characterized by the minrank parameter of a graph that represents the side information map of the receivers. Previous work has shown that it is $\mathsf {NP}$ -hard to determine the minrank parameter of graphs. In this work, we study the computational complexity of the minrank parameter on perturbed instances, obtained from worst-case instances by a random extension of the side information available to the receivers. This setting is motivated by applications of index coding, in which the side information is accumulated via repeated transmissions that suffer from loss of data due to noisy communication or storage capacity. We prove that determining the minrank parameter remains computationally hard on perturbed instances. Our contribution includes an extension of several hardness results of the minrank parameter to the perturbed setting as well as a general technique for deriving the hardness of the minrank parameter on perturbed instances from its hardness on worst-case instances.


  • Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank

    by Dror Chawin, Ishay Haviv

    The orthogonality dimension of a graph [Formula: see text] over [Formula: see text] is the smallest integer [Formula: see text] for which one can assign a nonzero [Formula: see text]-dimensional real vector to each vertex of [Formula: see text] such that every two adjacent vertices receive orthogonal vectors. We prove that for every sufficiently large integer [Formula: see text], it is [Formula: see text]-hard to decide whether the orthogonality dimension of a given graph over [Formula: see text] is at most [Formula: see text] or at least [Formula: see text]. We further prove such hardness results for the orthogonality dimension over finite fields as well as for the closely related minrank parameter, which is motivated by the index coding problem in information theory. This in particular implies that it is [Formula: see text]-hard to approximate these graph quantities to within any constant factor. Previously, the hardness of approximation was known to hold either assuming certain variants of the unique games conjecture or for approximation factors smaller than [Formula: see text]. The proofs involve the concept of line digraphs and bounds on their orthogonality dimension and on the minrank of their complement.