Research Interests
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

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.
Upper Bounds on the Boolean Rank of Kronecker Products
Ishay Haviv, Michal Parnas
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, to appear.

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.