6 papers · 1 filter
Kernelization Bounds for Constrained Coloring
Ishay Haviv
We study the kernel complexity of constraint satisfaction problems over a finite domain, parameterized by the number of variables, whose constraint language consists of two relatio…
New Hardness Results for Low-Rank Matrix Completion
Dror Chawin, Ishay Haviv
The low-rank matrix completion problem asks whether a given real matrix with missing values can be completed so that the resulting matrix has low rank or is close to a low-rank mat…
The Chromatic Number of Kneser Hypergraphs via Consensus Division
Ishay Haviv
We show that the Consensus Division theorem implies lower bounds on the chromatic number of Kneser hypergraphs, offering a novel proof for a result of Alon, Frankl, and Lovász (Tra…
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…
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…