Research Interests

Theoretical computer science, computational complexity, lattices, hardness of approximation, coding theory, combinatorics.

Theoretical computer science, computational complexity, lattices, hardness of approximation, coding theory, combinatorics.

Ishay Haviv

ישי חביב

Associate Professor

School of Computer Science

The Academic College of Tel Aviv-Yaffo

2 Rabenu Yerucham st., Tel Aviv-Yaffo 61083, Israel

Tel: (+972)-3-6803401

Email:*ishayhav at mta dot ac dot il*

Ph.D. in Computer Science (2011) at the Foundations of Computing Group,

Blavatnik School of Computer Science, Tel Aviv University.

The Ph.D. was supervised by Prof. Oded Regev and supported by the Adams

Fellowship Program of the Israel Academy of Sciences and Humanities.

School of Computer Science

The Academic College of Tel Aviv-Yaffo

2 Rabenu Yerucham st., Tel Aviv-Yaffo 61083, Israel

Tel: (+972)-3-6803401

Email:

Ph.D. in Computer Science (2011) at the Foundations of Computing Group,

Blavatnik School of Computer Science, Tel Aviv University.

The Ph.D. was supervised by Prof. Oded Regev and supported by the Adams

Fellowship Program of the Israel Academy of Sciences and Humanities.

Publications

• | A Fixed-Parameter Algorithm for the Schrijver Problem Ishay Haviv Manuscript. |

• | The Binary Rank of Circulant Block Matrices Ishay Haviv, Michal Parnas Manuscript. |

• | A Fixed-Parameter Algorithm for the Kneser Problem Ishay Haviv ICALP 2022, to appear. |

• | On the Binary and Boolean Rank of Regular Matrices Ishay Haviv, Michal Parnas Manuscript. |

• | Local Orthogonality Dimension Inon Attias, Ishay Haviv Manuscript. |

• | On the Subspace Choosability in Graphs Dror Chawin, Ishay Haviv Electronic Journal of Combinatorics, to appear. Preliminary version in EUROCOMB 2021. |

• | Upper Bounds on the Boolean Rank of Kronecker Products Ishay Haviv, Michal Parnas Discrete Applied Mathematics, to appear. Preliminary version in LAGOS 2021. |

• | The Complexity of Finding Fair Independent Sets in Cycles Ishay Haviv ITCS 2021. |

• | The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications Alexander Golovnev, Ishay Haviv CCC 2021. |

• | Minimizing the Alphabet Size of Erasure Codes with Restricted Decoding Sets Mira Gonen, Ishay Haviv, Michael Langberg, Alex Sprintson ISIT 2020. |

• | Task-based Solutions to Embedded Index Coding Ishay Haviv IEEE Transactions on Information Theory 66(10), pp. 6144-6149, 2020. |

• | Approximating the Orthogonality Dimension of Graphs and Hypergraphs Ishay Haviv MFCS 2019. |

• | Sum-free Sets of Integers with a Forbidden Sum Ishay Haviv SIAM Journal on Discrete Mathematics 33(1), pp. 402-424, 2019. |

• | Topological Bounds on the Dimension of Orthogonal Representations of Graphs Ishay Haviv European Journal of Combinatorics 81, pp. 84-97, 2019. |

• | On Minrank and Forbidden Subgraphs Ishay Haviv ACM Transactions on Computation Theory 11(4), Article 20, 2019. Preliminary version in RANDOM 2018. |

• | On Minrank and the Lovász Theta Function Ishay Haviv APPROX 2018. |

• | Dioid Partitions of Groups Ishay Haviv, Dan Levy European Journal of Combinatorics 73, pp. 211-230, 2018. |

• | Symmetric Complete Sum-free Sets in Cyclic Groups Ishay Haviv, Dan Levy Israel Journal of Mathematics 227(2), pp. 931-956, 2018. Preliminary version in EUROCOMB 2017. |

• | Non-linear Cyclic Codes that Attain the Gilbert-Varshamov Bound Ishay Haviv, Michael Langberg, Moshe Schwartz, Eitan Yaakobi ISIT 2017. |

• | The Restricted Isometry Property of Subsampled Fourier Matrices Ishay Haviv, Oded Regev GAFA Seminar Notes, pp. 163-179, 2017. Preliminary version in SODA 2016. |

• | The List-Decoding Size of Fourier-Sparse Boolean Functions Ishay Haviv, Oded Regev ACM Transactions on Computation Theory 8(3), Article 10, 2016. Preliminary version in CCC 2015. |

• | Sunflowers and Testing Triangle-Freeness of Functions Ishay Haviv, Ning Xie Computational Complexity 26(2), pp. 497-530, 2017. Preliminary version in ITCS 2015. |

• | On the Lattice Isomorphism Problem Ishay Haviv, Oded Regev SODA 2014. |

• | H-wise Independence
Ishay Haviv, Michael Langberg Chicago Journal of Theoretical Computer Science 2019(3), 2019. Preliminary version in ITCS 2013. |

• | The Remote Set Problem on Lattices
Ishay Haviv Computational Complexity 24(1), pp. 103-131, 2015. Preliminary version in APPROX 2012. |

• | Linear Index Coding via Semidefinite Programming Eden Chlamtac, Ishay Haviv Combinatorics, Probability & Computing 23(2), pp. 223-247, 2014. Preliminary version in SODA 2012. |

• | On Linear Index Coding for Random Graphs Ishay Haviv, Michael Langberg ISIT 2012. |

• | Beating the Gilbert-Varshamov Bound for Online Channels Ishay Haviv, Michael Langberg ISIT 2011. |

• | The Euclidean Distortion of Flat Tori Ishay Haviv, Oded Regev Journal of Topology and Analysis 5(2), pp. 205–223, 2013. Preliminary version in APPROX 2010. |

• | A Note on the Distribution of the Distance from a Lattice Ishay Haviv, Vadim Lyubashevsky, Oded Regev Discrete & Computational Geometry 41(1), pp. 162-176, 2009. |

• | Rounding Parallel Repetitions of Unique Games Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer FOCS 2008. |

• | Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors Ishay Haviv, Oded Regev Theory of Computing 8(23), pp. 513-531, 2012. Preliminary version in STOC 2007. |

• | On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy Ishay Haviv, Oded Regev, Amnon Ta-Shma Theory of Computing 3(3), pp. 45-60, 2007. |

• | Hardness of the Covering Radius Problem on Lattices Ishay Haviv, Oded Regev Chicago Journal of Theoretical Computer Science 2012(4), 2012. Preliminary version in CCC 2006. |