Research Interests

Theoretical computer science, computational complexity, algorithms, combinatorics, information theory, coding theory.

Theoretical computer science, computational complexity, algorithms, combinatorics, information theory, coding theory.

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,

School of Computer Science, Tel Aviv University, supervised by Prof. Oded Regev.

**If you are interested in collaboration, please contact me.**

Funding is available!

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,

School of Computer Science, Tel Aviv University, supervised by Prof. Oded Regev.

Funding is available!

Publications

• | Testing Intersectingness of Uniform Families Ishay Haviv, Michal Parnas RANDOM 2024, to appear. |

• | Larger Nearly Orthogonal Sets over Finite Fields Ishay Haviv, Sam Mattheus, Aleksa Milojević, Yuval Wigderson Manuscript. |

• | Nearly Orthogonal Sets over Finite Fields Dror Chawin, Ishay Haviv SoCG 2024. |

• | The Chromatic Number of Kneser Hypergraphs via Consensus Division Ishay Haviv ITCS 2024. |

• | On Finding Constrained Independent Sets in Cycles Ishay Haviv Algorithmica 86(4), pp. 1006-1030, 2024. Preliminary version in ICALP 2023. |

• | Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank Dror Chawin, Ishay Haviv SIAM Journal on Discrete Mathematics 37(4), pp. 2670-2688, 2023. Preliminary version in STACS 2023. |

• | Hardness of Linear Index Coding on Perturbed Instances Dror Chawin, Ishay Haviv IEEE Transactions on Information Theory 70(2), pp. 1388-1396, 2024. Preliminary version in Allerton 2022. |

• | Fixed-Parameter Algorithms for the Kneser and Schrijver Problems Ishay Haviv SIAM Journal on Computing 53(2), pp. 287-314, 2024. Preliminary versions in ICALP 2022 and IPEC 2022. |

• | The Binary Rank of Circulant Block Matrices Ishay Haviv, Michal Parnas Linear Algebra and its Applications 656, pp. 277-303, 2023. |

• | On the Binary and Boolean Rank of Regular Matrices Ishay Haviv, Michal Parnas Journal of Computer and System Sciences 134, pp. 73-86, 2023. Preliminary version in MFCS 2022. |

• | Local Orthogonality Dimension Inon Attias, Ishay Haviv Journal of Graph Theory 104(2), pp. 387-419, 2023. |

• | On the Subspace Choosability in Graphs Dror Chawin, Ishay Haviv Electronic Journal of Combinatorics 29(2), Article 20, 2022. Preliminary version in EUROCOMB 2021. |

• | Upper Bounds on the Boolean Rank of Kronecker Products Ishay Haviv, Michal Parnas Discrete Applied Mathematics 318, pp. 82-96, 2022. Preliminary version in LAGOS 2021. |

• | The Complexity of Finding Fair Independent Sets in Cycles Ishay Haviv Computational Complexity 31(2), Article 14, 2022. Preliminary version in ITCS 2021. |

• | The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications Alexander Golovnev, Ishay Haviv Theory of Computing 18(22), pp. 1-22, 2022. Preliminary version in CCC 2021. |

• | Minimizing the Alphabet Size in Codes with Restricted Error Sets Mira Gonen, Ishay Haviv, Michael Langberg, Alex Sprintson IEEE Transactions on Information Theory 70(6), pp. 3891-3902, 2024. Preliminary version in 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 Chicago Journal of Theoretical Computer Science 2022(2), 2022. Preliminary version in 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. |