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

Ishay Haviv
ישי חביב
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.
Publications
Symmetric Complete Sum-free Sets in Cyclic Groups
Ishay Haviv, Dan Levy
Manuscript.
Non-linear Cyclic Codes that Attain the Gilbert-Varshamov Bound
Ishay Haviv, Michael Langberg, Moshe Schwartz, Eitan Yaakobi
Manuscript.
The Restricted Isometry Property of Subsampled Fourier Matrices
Ishay Haviv, Oded Regev
GAFA Seminar Notes, to appear.
Preliminary version in SODA 2016.

The List-Decoding Size of Fourier-Sparse Boolean Functions
Ishay Haviv, Oded Regev
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, to appear.
Preliminary version in ITCS 2015.

On the Lattice Isomorphism Problem
Ishay Haviv, Oded Regev
SODA 2014.
H-wise Independence
Ishay Haviv, Michael Langberg
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.