10 papers
Minimizing the alphabet size of erasure codes with restricted decoding sets
Mira Gonen, Ishay Haviv, Michael Langberg +1
A Maximum Distance Separable code over an alphabet is defined via an encoding function that allows to retrieve a message from the codeword $…
Approximating the Orthogonality Dimension of Graphs and Hypergraphs
Ishay Haviv
A -dimensional orthogonal representation of a hypergraph is an assignment of nonzero vectors in to its vertices, such that every hyperedge contains two vertices w…
Task-based Solutions to Embedded Index Coding
Ishay Haviv
In the index coding problem a sender holds a message and wishes to broadcast information to receivers in a way that enables the th receiver to retrieve the…
Sum-free Sets of Integers with a Forbidden Sum
Ishay Haviv
A set of integers is sum-free if it contains no solution to the equation . We study sum-free subsets of the set of integers for which the integer …
Topological Bounds on the Dimension of Orthogonal Representations of Graphs
Ishay Haviv
An orthogonal representation of a graph is an assignment of nonzero real vectors to its vertices such that distinct non-adjacent vertices are assigned to orthogonal vectors. We pro…
Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
Ishay Haviv, Oded Regev
$ \newcommand{\SVP}{\mathsf{SVP}} \newcommand{\NP}{\mathsf{NP}} \newcommand{\RTIME}{\mathsf{RTIME}} \newcommand{\RSUBEXP}{\mathsf{RSUBEXP}} \newcommand{\eps}ε \newcommand{\poly}{\m…