Avner Magen

SODA Conference 2011 Conference Paper

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 ∊ ℝ n×m and B ∊ ℝ n×p be two matrices and ε > 0. We approximate the product A ⊤ B using two sketches and, where t ≪ n, such that with high probability. We analyze two different sampling procedures for constructing and; one of them is done by i. i. d. non-uniform sampling rows from A and B and the other by taking random linear combinations of their rows. We prove bounds on t that depend only on the intrinsic dimensionality of A and B, that is their rank and their stable rank. For achieving bounds that depend on rank when taking random linear combinations we employ standard tools from high-dimensional geometry such as concentration of measure arguments combined with elaborate ε-net constructions. For bounds that depend on the smaller parameter of stable rank this technology itself seems weak. However, we show that in combination with a simple truncation argument it is amenable to provide such bounds. To handle similar bounds for row sampling, we develop a novel matrix-valued Chernoff bound inequality which we call low rank matrix-valued Chernoff bound. Thanks to this inequality, we are able to give bounds that depend only on the stable rank of the input matrices. We highlight the usefulness of our approximate matrix multiplication bounds by supplying two applications. First we give an approximation algorithm for the ℓ 2 -regression problem that returns an approximate solution by randomly projecting the initial problem to dimensions linear on the rank of the constraint matrix. Second we give improved approximation algorithms for the low rank matrix approximation problem with respect to the spectral norm.

TCS Journal 2008 Journal Article

Analysis of set-up time models: A metric perspective

• Eitan Bachmat
• Tao Kai Lam
• Avner Magen

We consider model based estimates for set-up time. The general setting we are interested in is the following: given a disk and a sequence of read/write requests to certain locations, we would like to know the total time of transitions (set-up time) when these requests are served in an orderly fashion. The problem becomes nontrivial when we have, as is typically the case, only the counts of requests to each location rather then the whole input, and we can only hope to estimate the required time. Models that estimate set-up time have been suggested and heavily used as far back as the sixties. However, not much theory exists to enable a qualitative understanding of such models. To this end we introduce several properties such as (i) super-additivity which means that the set-up time estimate decreases as the input data is refined (ii) monotonicity which means that more activity produces more set-up time, (iii) Dominance which means that one model always produces higher estimates than a second model and (iv) approximation guarantees for the estimate with respect to the worst possible time, by which we can study different models. We provide criteria for super-additivity and monotonicity to hold for popular models such as the Partial Markov model (PMM). The criteria show that the estimate produced by these models will be monotone for any reasonable system. We also show that the independent reference model (IRM) based estimate functions as a worst case estimate in the sense that the estimate is guaranteed to be at least half of the actual set-up time. We also show that it dominates the PMM based estimates. Using our criteria we prove that PMM based estimates are always super additive when applied to the special metrics that correspond to seek times of disk drives. To establish our theoretical results we use the theory of finite metric spaces, and en route show a result of independent interest in that theory, which is a strengthening of a theorem of J. B. Kelly [J. B. Kelly, Hypermetric spaces and metric transforms, in: O. Shisha (Ed.), Inequalities III, 1972, pp. 149–158] about the properties of metrics that are formed by concave functions on the line.

FOCS Conference 2007 Conference Paper

Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy

• Konstantinos Georgiou
• Avner Magen
• Toniann Pitassi
• Iannis Tourlakis

Linear and semidefinite programming are highly successful approaches for obtaining good approximations for NP-hard optimization problems. For example, breakthrough approximation algorithms for Max Cut and Sparsest Cut use semidefinite programming. Perhaps the most prominent NP-hard problem whose exact approximation factor is still unresolved is Vertex Cover. PCP-based techniques of Dinur and Safra [7] show that it is not possible to achieve a factor better than 1. 36; on the other hand no known algorithm does better than the factor of 2 achieved by the simple greedy algorithm. Furthermore, there is a widespread belief that SDP technicptes are the most promising methods available for improving upon this factor of 2. Following a line of study initiated by Arora et al. [3], our aim is to show that a large family of LP and SDP based algorithms fail to produce an approximation for Vertex Cover better than 2. Lovasz and Schrijver [21] introduced the systems LS and LS + for systematically tightening LP and SDP relaxations, respectively, over many rounds. These systems naturally capture large classes of LP and SDP relaxations; indeed, LS + captures the celebrated SDP-based algorithms for Max Cur and Sparsest Cur mentioned above. We rule out polynomial-time 2 - Omega(lfloor) approximations for Vertex Cover using LS +. In particular, we prove an integrality gap of 2 - o(lfloor)for Vertex Cover SDPs obtained by tightening the standard LP relaxation with Omega(radiclog n/ log log n) rounds of LS +. While tight integrality gaps were known for Vertex Cover in the weaker LS system [23 ], previous results did not rule out a2 - Omega(1) approximation after even two rounds of LS +.

TCS Journal 2005 Journal Article

Simple permutations mix well

• Shlomo Hoory
• Avner Magen
• Steven Myers
• Charles Rackoff

We study the random composition of a small family of O ( n 3 ) simple permutations on { 0, 1 } n. Specifically, we ask what is the number of compositions needed to achieve a permutation that is close to k -wise independent. We improve on a result of Gowers [An almost m -wise independent random permutation of the cube, Combin. Probab. Comput. 5(2) (1996) 119–130] and show that up to a polylogarithmic factor, n 3 k 3 compositions of random permutations from this family suffice. We further show that the result applies to the stronger notion of k -wise independence against adaptive adversaries. This question is essentially about the rapid mixing of the random walk on a certain graph, and we approach it using a new technique to construct canonical paths. We also show that if we are willing to use a much larger family of simple permutations then we can guarantee closeness to k -wise independence with fewer compositions and fewer random bits.

STOC Conference 2003 Conference Paper

A sublinear algorithm for weakly approximating edit distance

• Tugkan Batu
• Funda Ergün
• Joe Kilian
• Avner Magen
• Sofya Raskhodnikova
• Ronitt Rubinfeld
• Rahul Sami

We show how to determine whether the edit distance between two given strings is small in sublinear time. Specifically, we present a test which, given two n-character strings A and B, runs in time o(n) and with high probability returns " CLOSE " if their edit distance is O(n Α ), and " FAR " if their edit distance is Ω(n), where Α is a fixed parameter less than 1. Our algorithm for testing the edit distance works by recursively subdividing the strings A and B into smaller substrings and looking for pairs of substrings in A, B with small edit distance. To do this, we query both strings at random places using a special technique for economizing on the samples which does not pick the samples independently and provides better query and overall complexity. As a result, our test runs in time Õ(n max(Α/2, 2Α - 1\) ) for any fixed Α < 1. Our algorithm thus provides a trade-off between accuracy and efficiency that is particularly useful when the input data is very large.We also show a lower bound of Ω(n Α/2 ) on the query complexity of every algorithm that distinguishes pairs of strings with edit distance at most n Α from those with edit distance at least n/6.

FOCS Conference 2003 Conference Paper

Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua

• Joshua Buresh-Oppenheim
• Nicola Galesi
• Shlomo Hoory
• Avner Magen
• Toniann Pitassi

We present a new method for proving rank lower bounds for Cutting Planes (CP) and several procedures based on lifting due to Lovasz and Schrijver (LS), when viewed as proof systems for unsatisfiability. We apply this method to obtain the following new results: first, we prove near-optimal rank bounds for Cutting Planes and Lovasz-Schrijver proofs for several prominent unsatisfiable CNF examples, including random kCNF formulas and the Tseitin graph formulas. It follows from these lower bounds that a linear number of rounds of CP or LS procedures when applied to relaxations of integer linear programs is not sufficient for reducing the integrality gap. Secondly, we give unsatisfiable examples that have constant rank CP and LS proofs but that require linear rank resolution proofs. Thirdly, we give examples where the CP rank is O(log n) but the LS rank is linear. Finally, we address the question of size versus rank: we show that, for both proof systems, rank does not accurately reflect proof size. Specifically, there are examples with polynomial-size CP/LS proofs, but requiring linear rank.

STOC Conference 2003 Conference Paper

Sublinear geometric algorithms

• Bernard Chazelle
• Ding Liu
• Avner Magen

SODA Conference 2003 Conference Paper

Sublinear-time approximation of Euclidean minimum spanning tree

• Artur Czumaj
• Funda Ergün
• Lance Fortnow
• Avner Magen
• Ilan Newman
• Ronitt Rubinfeld
• Christian Sohler

STOC Conference 2002 Conference Paper

Girth and euclidean distortion

• Nati Linial
• Avner Magen
• Assaf Naor

(MATH) In this paper we partially prove a conjecture that was raised by Linial, London and Rabinovich in \cite{llr}. Let $G$ be a $k$-regular graph, $k \ge 3$, with girth $g$. We show that every embedding $f : G \to \ell_2$ has distortion $\Omega (\sqrt{g})$. The original conjecture which remains open is that the Euclidean distortion is bounded below by $\Omega(g)$. Two proofs are given, one based on semi-definite programming, and the other on Markov Type, a concept that considers random walks on metrics.

STOC Conference 1998 Conference Paper

Trees and Euclidean Metrics

• Nati Linial
• Avner Magen
• Michael E. Saks