Publications

•	The Chromatic Number of Kneser Hypergraphs via Consensus Division Ishay Haviv ITCS 2024, to appear.
•	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 Allerton 2022.
•	A Fixed-Parameter Algorithm for the Schrijver Problem Ishay Haviv IPEC 2022.
•	The Binary Rank of Circulant Block Matrices Ishay Haviv, Michal Parnas Linear Algebra and its Applications 656, pp. 277-303, 2023.
•	A Fixed-Parameter Algorithm for the Kneser Problem Ishay Haviv ICALP 2022.
•	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 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 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.