dblp.uni-trier.dewww.uni-trier.de

Avner Magen Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo

*2009
33EEKonstantinos Georgiou, Avner Magen, Madhur Tulsiani: Optimal Sherali-Adams Gaps from Pairwise Independence. APPROX-RANDOM 2009: 125-139
32EEAvner Magen, Mohammad Moharrami: Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy. APPROX-RANDOM 2009: 258-271
2008
31EEAvner 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
29EEKonstantinos Georgiou, Avner Magen, Iannis Tourlakis: Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities. IPCO 2008: 140-153
28EEBernard Chazelle, Ding Liu, Avner Magen: Approximate range searching in higher dimension. Comput. Geom. 39(1): 24-29 (2008)
27EEEitan 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
26EEHamed 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
25EEKonstantinos 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
24EEAvner Magen: Dimensionality Reductions in l2 that Preserve Volumes and Distance to Affine Spaces. Discrete & Computational Geometry 38(1): 139-153 (2007)
2006
23EEShlomo Hoory, Avner Magen, Toniann Pitassi: Monotone Circuits for the Majority Function. APPROX-RANDOM 2006: 410-425
22EEEitan Bachmat, Tao-Kai Lam, Avner Magen: A Rigorous Analysis for Set-Up Time Models - A Metric Perspective. COCOON 2006: 387-397
21EEHamed 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)
20EEKonstantinos 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)
19EEJoshua 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
18EESpyros Angelopoulos, Atish Das Sarma, Avner Magen, Anastasios Viglas: On-Line Algorithms for Market Equilibria. COCOON 2005: 596-607
17EEAllan Borodin, David Cashman, Avner Magen: How Well Can Primal-Dual and Local-Ratio Algorithms Perform?. ICALP 2005: 943-955
16EEMichael 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
15EEBernard Chazelle, Ding Liu, Avner Magen: Sublinear Geometric Algorithms. Sublinear Algorithms 2005
14EEArtur 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)
13EEBernard Chazelle, Ding Liu, Avner Magen: Sublinear Geometric Algorithms. SIAM J. Comput. 35(3): 627-646 (2005)
12EEShlomo Hoory, Avner Magen, Steven Myers, Charles Rackoff: Simple permutations mix well. Theor. Comput. Sci. 348(2-3): 251-261 (2005)
2004
11EEDing Liu, Bernard Chazelle, Avner Magen: Approximate range searching in higher dimension. CCCG 2004: 154-157
10EEShlomo Hoory, Avner Magen, Steven Myers, Charles Rackoff: Simple Permutations Mix Well. ICALP 2004: 770-781
9EERobert Krauthgamer, Nathan Linial, Avner Magen: Metric Embeddings--Beyond One-Dimensional Distortion. Discrete & Computational Geometry 31(3): 339-356 (2004)
2003
8EEJosh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi: Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua. FOCS 2003: 318-
7EEArtur 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
6EETugkan 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
5EEBernard Chazelle, Ding Liu, Avner Magen: Sublinear geometric algorithms. STOC 2003: 531-540
2002
4EEAvner Magen: Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic Applications. RANDOM 2002: 239-253
3EENathan Linial, Avner Magen, Assaf Naor: Girth and euclidean distortion. STOC 2002: 705-711
2000
2EENathan 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
1EENathan Linial, Avner Magen, Michael E. Saks: Trees and Euclidean Metrics. STOC 1998: 169-175

Coauthor Index

1Michael Alekhnovich [16]
2Spyros Angelopoulos [18]
3Eitan Bachmat [22] [27]
4Tugkan Batu [6]
5Allan Borodin [16] [17]
6Joshua Buresh-Oppenheim (Josh Buresh-Oppenheim) [8] [16] [19]
7David Cashman [17]
8Bernard Chazelle [5] [11] [13] [15] [28]
9Artur Czumaj [7] [14]
10Funda Ergün [6] [7] [14]
11Lance Fortnow [7] [14]
12Nicola Galesi [8] [19]
13Konstantinos Georgiou [20] [25] [29] [33]
14Hamed Hatami [21] [26]
15Shlomo Hoory [8] [10] [12] [19] [23]
16Russell Impagliazzo [16]
17Joe Kilian [6]
18Robert Krauthgamer [9]
19Tao-Kai Lam [22] [27]
20Nathan Linial (Nati Linial) [1] [2] [3] [9]
21Ding Liu [5] [11] [13] [15] [28]
22Evangelos Markakis (Vangelis Markakis) [21] [26]
23Mohammad Moharrami [30] [32]
24Steven Myers [10] [12]
25Assaf Naor [3]
26Ilan Newman [7] [14]
27Toniann Pitassi [8] [16] [19] [20] [23] [25]
28Charles Rackoff [10] [12]
29Sofya Raskhodnikova [6]
30Ronitt Rubinfeld [6] [7] [14]
31Michael E. Saks [1]
32Rahul Sami [6]
33Atish Das Sarma [18]
34Christian Sohler [7] [14]
35Iannis Tourlakis [20] [25] [29]
36Madhur Tulsiani [33]
37Anastasios Viglas [18]
38Anastasios Zouzias [31]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)