48 citations · 68 across the 25 of their papers we have counts for
6 papers · 1 filter
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…
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
Ishay Haviv, Oded Regev, Amnon Ta-Shma
$ \newcommand{\eps}ε \newcommand{\NP}{\mathsf{NP}} \newcommand{\YES}{\mathsf{YES}} \newcommand{\NO}{\mathsf{NO}} \newcommand{\myminus}{\text{-}}\newcommand{\Bsat}{\mathsf{B}} \newc…
On Minrank and Forbidden Subgraphs
Ishay Haviv
The minrank over a field of a graph on the vertex set is the minimum possible rank of a matrix such that $M_{i,i…
On Minrank and the Lovász Theta Function
Ishay Haviv
Two classical upper bounds on the Shannon capacity of graphs are the -function due to Lovász and the minrank parameter due to Haemers. We provide several explicit constr…