Avner Magen

According to our database, Avner Magen authored at least 41 papers between 1998 and 2012.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2012

SDP Gaps from Pairwise Independence.

Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, Madhur Tulsiani

Theory Comput., 2012

On Quadratic Threshold CSPs.

Per Austrin, Siavosh Benabbas, Avner Magen

Discret. Math. Theor. Comput. Sci., 2012

2011

How well can primal-dual and local-ratio algorithms perform?

Allan Borodin, David Cashman, Avner Magen

ACM Trans. Algorithms, 2011

Toward a Model for Backtracking and Dynamic Programming.

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi

Comput. Complex., 2011

Low Rank Matrix-valued Chernoff Bounds and Approximate Matrix Multiplication.

Avner Magen, Anastasios Zouzias

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy.

Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou, Avner Magen

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

2010

Integrality Gaps of 2-o(1) for Vertex Cover SDPs in the Lov[a-acute]sz--Schrijver Hierarchy.

Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis

SIAM J. Comput., 2010

The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs.

Siavosh Benabbas, Konstantinos Georgiou, Avner Magen

Electron. Colloquium Comput. Complex., 2010

Low Rank Matrix-Valued Chernoff Bounds and Applications

Avner Magen, Anastasios Zouzias

CoRR, 2010

Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain.

Siavosh Benabbas, Avner Magen

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

Online Embeddings.

Piotr Indyk, Avner Magen, Anastasios Sidiropoulos, Anastasios Zouzias

Proceedings of the Approximation, 2010

2009

Optimal Sherali-Adams Gaps from Pairwise Independence.

Konstantinos Georgiou, Avner Magen, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2009

Toward a Model for Backtracking and Dynamic Programming.

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen

Electron. Colloquium Comput. Complex., 2009

On the Tightening of the Standard SDP for Vertex Cover with $ell_1$ Inequalities.

Konstantinos Georgiou, Avner Magen, Iannis Tourlakis

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy.

Avner Magen, Mohammad Moharrami

Proceedings of the Approximation, 2009

2008

Analysis of set-up time models: A metric perspective.

Eitan Bachmat, Tao-Kai Lam, Avner Magen

Theor. Comput. Sci., 2008

Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to l₁ Embeddability of Negative Type Metrics.

Hamed Hatami, Avner Magen, Evangelos Markakis

SIAM J. Discret. Math., 2008

Approximate range searching in higher dimension.

Bernard Chazelle, Ding Liu, Avner Magen

Comput. Geom., 2008

Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities.

Konstantinos Georgiou, Avner Magen, Iannis Tourlakis

Proceedings of the Integer Programming and Combinatorial Optimization, 2008

On the nonexistence of dimension reduction for ℓ2₂ metrics.

Mohammad Moharrami, Avner Magen

Proceedings of the 20th Annual Canadian Conference on Computational Geometry, 2008

Near Optimal Dimensionality Reductions That Preserve Volumes.

Avner Magen, Anastasios Zouzias

Proceedings of the Approximation, 2008

2007

Dimensionality Reductions in <i>l</i>₂ that Preserve Volumes and Distance to Affine Spaces.

Avner Magen

Discret. Comput. Geom., 2007

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

Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to <i>l</i>₁ Embeddability of Negative Type Metrics.

Hamed Hatami, Avner Magen, Evangelos Markakis

Proceedings of the Approximation, 2007

2006

Rank Bounds and Integrality Gaps for Cutting Planes Procedures.

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

Theory Comput., 2006

Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy.

Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis

Electron. Colloquium Comput. Complex., 2006

A Rigorous Analysis for Set-Up Time Models - A Metric Perspective.

Eitan Bachmat, Tao-Kai Lam, Avner Magen

Proceedings of the Computing and Combinatorics, 12th Annual International Conference, 2006

Monotone Circuits for the Majority Function.

Shlomo Hoory, Avner Magen, Toniann Pitassi

Proceedings of the Approximation, 2006

2005

Simple permutations mix well.

Shlomo Hoory, Avner Magen, Steven A. Myers, Charles Rackoff

Theor. Comput. Sci., 2005

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time.

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

SIAM J. Comput., 2005

Sublinear Geometric Algorithms.

Bernard Chazelle, Ding Liu, Avner Magen

SIAM J. Comput., 2005

On-Line Algorithms for Market Equilibria.

Spyros Angelopoulos, Atish Das Sarma, Avner Magen, Anastasios Viglas

Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004

Metric Embeddings--Beyond One-Dimensional Distortion.

Robert Krauthgamer, Nathan Linial, Avner Magen

Discret. Comput. Geom., 2004

2003

A sublinear algorithm for weakly approximating edit distance.

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

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Sublinear-time approximation of Euclidean minimum spanning tree.

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

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua.

Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

Girth and euclidean distortion.

Nathan Linial, Avner Magen, Assaf Naor

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic Applications.

Avner Magen

Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

2001

On the Euclidicity of metric spaces.

Avner Magen

PhD thesis, 2001

2000

Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders.

Nathan Linial, Avner Magen

J. Comb. Theory B, 2000

1998

Trees and Euclidean Metrics.

Nathan Linial, Avner Magen, Michael E. Saks

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998