2008 | ||
---|---|---|
31 | EE | Avner Magen, Anastasios Zouzias: Near Optimal Dimensionality Reductions That Preserve Volumes. APPROX-RANDOM 2008: 523-534 |
30 | Mohammad Moharrami, Avner Magen: On the nonexistence of dimension reduction for $\ell2_2$ metrics. CCCG 2008 | |
29 | EE | Konstantinos Georgiou, Avner Magen, Iannis Tourlakis: Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities. IPCO 2008: 140-153 |
28 | EE | Bernard Chazelle, Ding Liu, Avner Magen: Approximate range searching in higher dimension. Comput. Geom. 39(1): 24-29 (2008) |
27 | EE | Eitan Bachmat, Tao-Kai Lam, Avner Magen: Analysis of set-up time models: A metric perspective. Theor. Comput. Sci. 401(1-3): 172-180 (2008) |
2007 | ||
26 | EE | Hamed Hatami, Avner Magen, Evangelos Markakis: Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to l1 Embeddability of Negative Type Metrics. APPROX-RANDOM 2007: 164-179 |
25 | EE | Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis: Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy. FOCS 2007: 702-712 |
24 | EE | Avner Magen: Dimensionality Reductions in l2 that Preserve Volumes and Distance to Affine Spaces. Discrete & Computational Geometry 38(1): 139-153 (2007) |
2006 | ||
23 | EE | Shlomo Hoory, Avner Magen, Toniann Pitassi: Monotone Circuits for the Majority Function. APPROX-RANDOM 2006: 410-425 |
22 | EE | Eitan Bachmat, Tao-Kai Lam, Avner Magen: A Rigorous Analysis for Set-Up Time Models - A Metric Perspective. COCOON 2006: 387-397 |
21 | EE | Hamed Hatami, Avner Magen, Vangelis Markakis: Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics CoRR abs/cs/0601011: (2006) |
20 | EE | Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis: Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy. Electronic Colloquium on Computational Complexity (ECCC) 13(152): (2006) |
19 | EE | Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi: Rank Bounds and Integrality Gaps for Cutting Planes Procedures. Theory of Computing 2(1): 65-90 (2006) |
2005 | ||
18 | EE | Spyros Angelopoulos, Atish Das Sarma, Avner Magen, Anastasios Viglas: On-Line Algorithms for Market Equilibria. COCOON 2005: 596-607 |
17 | EE | Allan Borodin, David Cashman, Avner Magen: How Well Can Primal-Dual and Local-Ratio Algorithms Perform?. ICALP 2005: 943-955 |
16 | EE | Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi: Toward a Model for Backtracking and Dynamic Programming. IEEE Conference on Computational Complexity 2005: 308-322 |
15 | EE | Bernard Chazelle, Ding Liu, Avner Magen: Sublinear Geometric Algorithms. Sublinear Algorithms 2005 |
14 | EE | Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler: Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time. SIAM J. Comput. 35(1): 91-109 (2005) |
13 | EE | Bernard Chazelle, Ding Liu, Avner Magen: Sublinear Geometric Algorithms. SIAM J. Comput. 35(3): 627-646 (2005) |
12 | EE | Shlomo Hoory, Avner Magen, Steven Myers, Charles Rackoff: Simple permutations mix well. Theor. Comput. Sci. 348(2-3): 251-261 (2005) |
2004 | ||
11 | EE | Ding Liu, Bernard Chazelle, Avner Magen: Approximate range searching in higher dimension. CCCG 2004: 154-157 |
10 | EE | Shlomo Hoory, Avner Magen, Steven Myers, Charles Rackoff: Simple Permutations Mix Well. ICALP 2004: 770-781 |
9 | EE | Robert Krauthgamer, Nathan Linial, Avner Magen: Metric Embeddings--Beyond One-Dimensional Distortion. Discrete & Computational Geometry 31(3): 339-356 (2004) |
2003 | ||
8 | EE | Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi: Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua. FOCS 2003: 318- |
7 | EE | Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler: Sublinear-time approximation of Euclidean minimum spanning tree. SODA 2003: 813-822 |
6 | EE | Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami: A sublinear algorithm for weakly approximating edit distance. STOC 2003: 316-324 |
5 | EE | Bernard Chazelle, Ding Liu, Avner Magen: Sublinear geometric algorithms. STOC 2003: 531-540 |
2002 | ||
4 | EE | Avner Magen: Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic Applications. RANDOM 2002: 239-253 |
3 | EE | Nathan Linial, Avner Magen, Assaf Naor: Girth and euclidean distortion. STOC 2002: 705-711 |
2000 | ||
2 | EE | Nathan Linial, Avner Magen: Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders. J. Comb. Theory, Ser. B 79(2): 157-171 (2000) |
1998 | ||
1 | EE | Nathan Linial, Avner Magen, Michael E. Saks: Trees and Euclidean Metrics. STOC 1998: 169-175 |