Ishay Haviv

CoRR, July, 2025

Kernels for storage capacity and dual index coding.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. A, 2025

Larger nearly orthogonal sets over finite fields.

[BibT_eX]

[DOI]

Discret. Math., 2025

A near-optimal kernel for a coloring problem.

[BibT_eX]

[DOI]

Dror Rabinovich

Discret. Appl. Math., 2025

New Hardness Results for Low-Rank Matrix Completion.

[BibT_eX]

[DOI]

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

2024

Improved Approximation Algorithms for Index Coding.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, November, 2024

Minimizing the Alphabet Size in Codes With Restricted Error Sets.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, June, 2024

Fixed-Parameter Algorithms for the Kneser and Schrijver Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2024

Kernelization for Orthogonality Dimension.

[BibT_eX]

[DOI]

Dror Rabinovich

Proceedings of the 19th International Symposium on Parameterized and Exact Computation, 2024

The Chromatic Number of Kneser Hypergraphs via Consensus Division.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Nearly Orthogonal Sets over Finite Fields.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Computational Geometry, 2024

Testing Intersectingness of Uniform Families.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

Local orthogonality dimension.

[BibT_eX]

[DOI]

Inon Attias

J. Graph Theory, October, 2023

Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

On Finding Constrained Independent Sets in Cycles.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

The Binary Rank of Circulant Block Matrices.

[BibT_eX]

[DOI]

CoRR, 2022

On the Subspace Choosability in Graphs.

[BibT_eX]

[DOI]

Electron. J. Comb., 2022

On the Binary and Boolean Rank of Regular Matrices.

[BibT_eX]

[DOI]

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

A Fixed-Parameter Algorithm for the Schrijver Problem.

[BibT_eX]

[DOI]

Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

A Fixed-Parameter Algorithm for the Kneser Problem.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Hardness of Linear Index Coding on Perturbed Instances.

[BibT_eX]

[DOI]

Proceedings of the 58th Annual Allerton Conference on Communication, 2022

2021

Upper Bounds on the Boolean Rank of Kronecker Products.

[BibT_eX]

[DOI]

Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, 2021

The Complexity of Finding Fair Independent Sets in Cycles.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications.

[BibT_eX]

[DOI]

Alexander Golovnev

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Task-Based Solutions to Embedded Index Coding.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2020

Minimizing the alphabet size of erasure codes with restricted decoding sets.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2020

2019

Sum-Free Sets of Integers with a Forbidden Sum.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2019

Topological bounds on the dimension of orthogonal representations of graphs.

[BibT_eX]

[DOI]

Eur. J. Comb., 2019

Approximating the Orthogonality Dimension of Graphs and Hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

2018

Dioid partitions of groups.

[BibT_eX]

[DOI]

Dan Levy

Eur. J. Comb., 2018

On Minrank and Forbidden Subgraphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

On Minrank and the Lovász Theta Function.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

Symmetric Complete Sum-free Sets in Cyclic Groups.

[BibT_eX]

[DOI]

Dan Levy

Electron. Notes Discret. Math., 2017

Non-linear cyclic codes that attain the Gilbert-Varshamov bound.

[BibT_eX]

[DOI]

Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

2016

The Restricted Isometry Property of Subsampled Fourier Matrices.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Sunflowers and Testing Triangle-Freeness of Functions.

[BibT_eX]

[DOI]

Ning Xie

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

The List-Decoding Size of Fourier-Sparse Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

On the Lattice Isomorphism Problem.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013

H-wise independence.

[BibT_eX]

[DOI]

Michael Langberg

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Linear index coding via semidefinite programming.

[BibT_eX]

[DOI]

Eden Chlamtac

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

On linear index coding for random graphs.

[BibT_eX]

[DOI]

Michael Langberg

Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012

The Remote Set Problem on Lattices.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Lattices and codes

[BibT_eX]

[DOI]

PhD thesis, 2011

Beating the Gilbert-Varshamov bound for online channels.

[BibT_eX]

[DOI]

Michael Langberg

Proceedings of the 2011 IEEE International Symposium on Information Theory Proceedings, 2011

2010

The Euclidean Distortion of Flat Tori.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

2009

A Note on the Distribution of the Distance from a Lattice.

[BibT_eX]

[DOI]

Vadim Lyubashevsky

Discret. Comput. Geom., 2009

2008

Rounding Parallel Repetitions of Unique Games.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy.

[BibT_eX]

[DOI]

Amnon Ta-Shma

Theory Comput., 2007

Tensor-based hardness of the shortest vector problem to within almost polynomial factors.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

Hardness of the Covering Radius Problem on Lattices.

[BibT_eX]

[DOI]