Ishay Haviv

MFCS Conference 2025 Conference Paper

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 matrix. The completed matrix is often required to satisfy additional structural constraints, such as positive semi-definiteness or a bounded infinity norm. The problem arises in various research fields, including machine learning, statistics, and theoretical computer science, and has broad real-world applications. This paper presents new NP-hardness results for low-rank matrix completion problems. We show that for every sufficiently large integer d and any real number ε ∈ [2^{-O(d)}, 1/7], given a partial matrix A with exposed values of magnitude at most 1 that admits a positive semi-definite completion of rank d, it is NP-hard to find a positive semi-definite matrix that agrees with each given value of A up to an additive error of at most ε, even when the rank is allowed to exceed d by a multiplicative factor of O (1/(ε²⋅log(1/ε))). This strengthens a result of Hardt, Meka, Raghavendra, and Weitz (COLT, 2014), which applies to multiplicative factors smaller than 2 and to ε that decays polynomially in d. We establish similar NP-hardness results for the case where the completed matrix is constrained to have a bounded infinity norm (rather than be positive semi-definite), for which all previous hardness results rely on complexity assumptions related to the Unique Games Conjecture. Our proofs involve a novel notion of nearly orthonormal representations of graphs, the concept of line digraphs, and bounds on the rank of perturbed identity matrices.

MFCS Conference 2022 Conference Paper

On the Binary and Boolean Rank of Regular Matrices

• Ishay Haviv
• Michal Parnas

A 0, 1 matrix is said to be regular if all of its rows and columns have the same number of ones. We prove that for infinitely many integers k, there exists a square regular 0, 1 matrix with binary rank k, such that the Boolean rank of its complement is k^Ω̃(log k). Equivalently, the ones in the matrix can be partitioned into k combinatorial rectangles, whereas the number of rectangles needed for any cover of its zeros is k^Ω̃(log k). This settles, in a strong form, a question of Pullman (Linear Algebra Appl. , 1988) and a conjecture of Hefner, Henson, Lundgren, and Maybee (Congr. Numer. , 1990). The result can be viewed as a regular analogue of a recent result of Balodis, Ben-David, Göös, Jain, and Kothari (FOCS, 2021), motivated by the clique vs. independent set problem in communication complexity and by the (disproved) Alon-Saks-Seymour conjecture in graph theory. As an application of the produced regular matrices, we obtain regular counterexamples to the Alon-Saks-Seymour conjecture and prove that for infinitely many integers k, there exists a regular graph with biclique partition number k and chromatic number k^Ω̃(log k).

MFCS Conference 2019 Conference Paper

Approximating the Orthogonality Dimension of Graphs and Hypergraphs

• Ishay Haviv

A t-dimensional orthogonal representation of a hypergraph is an assignment of nonzero vectors in R^t to its vertices, such that every hyperedge contains two vertices whose vectors are orthogonal. The orthogonality dimension of a hypergraph H, denoted by overline{xi}(H), is the smallest integer t for which there exists a t-dimensional orthogonal representation of H. In this paper we study computational aspects of the orthogonality dimension of graphs and hypergraphs. We prove that for every k >= 4, it is NP-hard (resp. quasi-NP-hard) to distinguish n-vertex k-uniform hypergraphs H with overline{xi}(H) <= 2 from those satisfying overline{xi}(H) >= Omega(log^delta n) for some constant delta>0 (resp. overline{xi}(H) >= Omega(log^{1-o(1)} n)). For graphs, we relate the NP-hardness of approximating the orthogonality dimension to a variant of a long-standing conjecture of Stahl. We also consider the algorithmic problem in which given a graph G with overline{xi}(G) <= 3 the goal is to find an orthogonal representation of G of as low dimension as possible, and provide a polynomial time approximation algorithm based on semidefinite programming.

SODA Conference 2016 Conference Paper

The Restricted Isometry Property of Subsampled Fourier Matrices

• Ishay Haviv
• Oded Regev 0001

SODA Conference 2014 Conference Paper

On the Lattice Isomorphism Problem

• Ishay Haviv
• Oded Regev 0001

We study the Lattice Isomorphism Problem (LIP), in which given two lattices ℒ 1 and ℒ 2 the goal is to decide whether there exists an orthogonal linear transformation mapping L 1 to ℒ 2. Our main result is an algorithm for this problem running in time n O ( n ) times a polynomial in the input size, where n is the rank of the input lattices. A crucial component is a new generalized isolation lemma, which can isolate n linearly independent vectors in a given subset of ℤ n and might be useful elsewhere. We also prove that LIP lies in the complexity class SZK.

SODA Conference 2012 Conference Paper

Linear index coding via semidefinite programming

• Eden Chlamtac
• Ishay Haviv

FOCS Conference 2008 Conference Paper

Rounding Parallel Repetitions of Unique Games

• Boaz Barak
• Moritz Hardt
• Ishay Haviv
• Anup Rao 0001
• Oded Regev 0001
• David Steurer

We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Specifically, denoting by val(G) the value of a two-prover unique game G, andby sdpval(G) the value of a natural semidefinite program to approximate val(G), we prove that for every l epsi N, if sdpval(G) ges 1-delta, then val(G l ) ges 1-radicsldelta. Here, G l denotes the l-fold parallel repetition of G, and s=O(log(k/delta)), where k denotes the alphabet size of the game. For the special case where G is an XOR game (i. e. , k=2), we obtain the same bound but with s as an absolute constant. Our bounds on s are optimal up to a factor of O(log(1/delta)). For games with a significant gap between the quantities val(G) and sdpval(G), our result implies that val(G l ) may be much larger than val(G) l, giving a counterexample to the strong parallel repetition conjecture. In a recent breakthrough, Raz (FOCS'08) has shown such an example using the max-cut game on oddcycles. Our results are based on a generalization of his techniques.

STOC Conference 2007 Conference Paper

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

• Ishay Haviv
• Oded Regev 0001

We show that unless NP ⊆ RTIME (2 poly(log n) ), for any ε > 0 there is no polynomial-time algorithm approximating the Shortest Vector Problem (SVP) on n -dimensional lattices inthe l p norm (1 ≤q p 0.