Avner Magen

Publication Activity (10 Years)

Years Active: 1998-2012
Publications (10 Years): 0

Top Topics

Dissimilarity Matrix

Threshold Values

Independence Assumption

Top Venues

Discret. Math. Theor. Comput. Sci.

Publications

Per Austrin, Siavosh Benabbas, Avner Magen
On Quadratic Threshold CSPs. Discret. Math. Theor. Comput. Sci. 14 (2) (2012)
Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, Madhur Tulsiani
SDP Gaps from Pairwise Independence. Theory Comput. 8 (1) (2012)
Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou, Avner Magen
Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy. FSTTCS (2011)
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
Toward a Model for Backtracking and Dynamic Programming. Comput. Complex. 20 (4) (2011)
Avner Magen, Anastasios Zouzias
Low Rank Matrix-valued Chernoff Bounds and Approximate Matrix Multiplication. SODA (2011)
Allan Borodin, David Cashman, Avner Magen
How well can primal-dual and local-ratio algorithms perform? ACM Trans. Algorithms 7 (3) (2011)
Siavosh Benabbas, Avner Magen
Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain. IPCO (2010)
Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis
Integrality Gaps of 2-o(1) for Vertex Cover SDPs in the Lov[a-acute]sz--Schrijver Hierarchy. SIAM J. Comput. 39 (8) (2010)
Siavosh Benabbas, Konstantinos Georgiou, Avner Magen
The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs. Electron. Colloquium Comput. Complex. 17 (2010)
Piotr Indyk, Avner Magen, Anastasios Sidiropoulos, Anastasios Zouzias
Online Embeddings. APPROX-RANDOM (2010)
Per Austrin, Siavosh Benabbas, Avner Magen
On Quadratic Threshold CSPs. LATIN (2010)
Avner Magen, Anastasios Zouzias
Low Rank Matrix-Valued Chernoff Bounds and Applications CoRR (2010)
Konstantinos Georgiou, Avner Magen, Iannis Tourlakis
On the Tightening of the Standard SDP for Vertex Cover with $ell_1$ Inequalities. FSTTCS (2009)
Avner Magen, Mohammad Moharrami
Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy. APPROX-RANDOM (2009)
Konstantinos Georgiou, Avner Magen, Madhur Tulsiani
Optimal Sherali-Adams Gaps from Pairwise Independence. Electron. Colloquium Comput. Complex. 16 (2009)
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen
Toward a Model for Backtracking and Dynamic Programming. Electron. Colloquium Comput. Complex. 16 (2009)
Konstantinos Georgiou, Avner Magen, Madhur Tulsiani
Optimal Sherali-Adams Gaps from Pairwise Independence. APPROX-RANDOM (2009)
Mohammad Moharrami, Avner Magen
metrics. CCCG (2008)
Eitan Bachmat, Tao-Kai Lam, Avner Magen
Analysis of set-up time models: A metric perspective. Theor. Comput. Sci. 401 (1-3) (2008)
Bernard Chazelle, Ding Liu, Avner Magen
Approximate range searching in higher dimension. Comput. Geom. 39 (1) (2008)
Konstantinos Georgiou, Avner Magen, Iannis Tourlakis
Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities. IPCO (2008)
Avner Magen, Anastasios Zouzias
Near Optimal Dimensionality Reductions That Preserve Volumes. APPROX-RANDOM (2008)
Hamed Hatami, Avner Magen, Evangelos Markakis
Embeddability of Negative Type Metrics. SIAM J. Discret. Math. 23 (1) (2008)
Hamed Hatami, Avner Magen, Evangelos Markakis
Embeddability of Negative Type Metrics. APPROX-RANDOM (2007)
Avner Magen
that Preserve Volumes and Distance to Affine Spaces. Discret. Comput. Geom. 38 (1) (2007)
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)
Hamed Hatami, Avner Magen, Vangelis Markakis
embeddability of Negative Type metrics CoRR (2006)
Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis
Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy. Electron. Colloquium Comput. Complex. 13 (152) (2006)
Eitan Bachmat, Tao-Kai Lam, Avner Magen
A Rigorous Analysis for Set-Up Time Models - A Metric Perspective. COCOON (2006)
Shlomo Hoory, Avner Magen, Toniann Pitassi
Monotone Circuits for the Majority Function. APPROX-RANDOM (2006)
Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi
Rank Bounds and Integrality Gaps for Cutting Planes Procedures. Theory Comput. 2 (4) (2006)
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
Toward a Model for Backtracking and Dynamic Programming. Computational Complexity Conference (2005)
Bernard Chazelle, Ding Liu, Avner Magen
Sublinear Geometric Algorithms. Sublinear Algorithms (2005)
Allan Borodin, David Cashman, Avner Magen
How Well Can Primal-Dual and Local-Ratio Algorithms Perform?. ICALP (2005)
Bernard Chazelle, Ding Liu, Avner Magen
Sublinear Geometric Algorithms. SIAM J. Comput. 35 (3) (2005)
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) (2005)
Spyros Angelopoulos, Atish Das Sarma, Avner Magen, Anastasios Viglas
On-Line Algorithms for Market Equilibria. COCOON (2005)
Shlomo Hoory, Avner Magen, Steven A. Myers, Charles Rackoff
Simple permutations mix well. Theor. Comput. Sci. 348 (2-3) (2005)
Shlomo Hoory, Avner Magen, Steven A. Myers, Charles Rackoff
Simple Permutations Mix Well. ICALP (2004)
Ding Liu, Bernard Chazelle, Avner Magen
Approximate range searching in higher dimension. CCCG (2004)
Robert Krauthgamer, Nathan Linial, Avner Magen
Metric Embeddings--Beyond One-Dimensional Distortion. Discret. Comput. Geom. 31 (3) (2004)
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)
Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi
Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua. FOCS (2003)
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)
Bernard Chazelle, Ding Liu, Avner Magen
Sublinear geometric algorithms. STOC (2003)
Nathan Linial, Avner Magen, Assaf Naor
Girth and euclidean distortion. STOC (2002)
Avner Magen
Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic Applications. RANDOM (2002)
Nathan Linial, Avner Magen
Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders. J. Comb. Theory, Ser. B 79 (2) (2000)
Nathan Linial, Avner Magen, Michael E. Saks
Trees and Euclidean Metrics. STOC (1998)