Research Interests
 
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!
Publications
Nearly Orthogonal Sets over Finite Fields
Dror Chawin, Ishay Haviv
SoCG 2024, to appear.
The Chromatic Number of Kneser Hypergraphs via Consensus Division
Ishay Haviv
ITCS 2024.
On Finding Constrained Independent Sets in Cycles
Ishay Haviv
Algorithmica, to appear.
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, to appear.
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, to appear.
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.