2 papers
cs.DS2010
Low Rank Matrix-Valued Chernoff Bounds and Approximate Matrix Multiplication
Avner Magen, Anastasios Zouzias
In this paper we develop algorithms for approximating matrix multiplication with respect to the spectral norm. Let A\in{\RR^{n\times m}} and B\in\RR^{n \times p} be two matrices an…
cs.DS2006
Integrality gaps of semidefinite programs for Vertex Cover and relations to embeddability of Negative Type metrics
Hamed Hatami, Avner Magen, Vangelis Markakis
We study various SDP formulations for {\sc Vertex Cover} by adding different constraints to the standard formulation. We show that {\sc Vertex Cover} cannot be approximated better…