Avner Magen

50 papers A* 10A 1B 3Misc 2Journal 21Unranked 12
YearRankTypeTitle / Venue / Authors
2012 J jnl
On Quadratic Threshold CSPs.
Discret. Math. Theor. Comput. Sci.
Per Austrin, Siavosh Benabbas, Avner Magen
2012 J jnl
SDP Gaps from Pairwise Independence.
Theory Comput.
Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, Madhur Tulsiani
2011 J jnl
How well can primal-dual and local-ratio algorithms perform?
ACM Trans. Algorithms
Allan Borodin, David Cashman, Avner Magen
2011 A* conf
Low Rank Matrix-valued Chernoff Bounds and Approximate Matrix Multiplication.
SODA
Avner Magen, Anastasios Zouzias
2011 — conf
Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy.
FSTTCS
Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou, Avner Magen
2011 J jnl
Toward a Model for Backtracking and Dynamic Programming.
Comput. Complex.
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
2010 B conf
Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain.
IPCO
Siavosh Benabbas, Avner Magen
2010 J jnl
Integrality Gaps of 2-o(1) for Vertex Cover SDPs in the Lov[a-acute]sz--Schrijver Hierarchy.
SIAM J. Comput.
Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis
2010 J jnl
Low Rank Matrix-Valued Chernoff Bounds and Applications
CoRR
Avner Magen, Anastasios Zouzias
2010 B conf
On Quadratic Threshold CSPs.
LATIN
Per Austrin, Siavosh Benabbas, Avner Magen
2010 — conf
Online Embeddings.
APPROX-RANDOM
Piotr Indyk, Avner Magen, Anastasios Sidiropoulos, Anastasios Zouzias
2010 J jnl
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.
Siavosh Benabbas, Konstantinos Georgiou, Avner Magen
2009 — conf
On the Tightening of the Standard SDP for Vertex Cover with $ell_1$ Inequalities.
FSTTCS
Konstantinos Georgiou, Avner Magen, Iannis Tourlakis
2009 — conf
Optimal Sherali-Adams Gaps from Pairwise Independence.
APPROX-RANDOM
Konstantinos Georgiou, Avner Magen, Madhur Tulsiani
2009 J jnl
Optimal Sherali-Adams Gaps from Pairwise Independence.
Electron. Colloquium Comput. Complex.
Konstantinos Georgiou, Avner Magen, Madhur Tulsiani
2009 — conf
Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy.
APPROX-RANDOM
Avner Magen, Mohammad Moharrami
2009 J jnl
Toward a Model for Backtracking and Dynamic Programming.
Electron. Colloquium Comput. Complex.
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen
2008 J jnl
Analysis of set-up time models: A metric perspective.
Theor. Comput. Sci.
Eitan Bachmat, Tao-Kai Lam, Avner Magen
2008 J jnl
Approximate range searching in higher dimension.
Comput. Geom.
Bernard Chazelle, Ding Liu, Avner Magen
2008 J jnl
Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to l
SIAM J. Discret. Math.
Hamed Hatami, Avner Magen, Evangelos Markakis
2008 — conf
Near Optimal Dimensionality Reductions That Preserve Volumes.
APPROX-RANDOM
Avner Magen, Anastasios Zouzias
2008 — conf
On the nonexistence of dimension reduction for ℓ2
CCCG
Mohammad Moharrami, Avner Magen
2008 B conf
Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities.
IPCO
Konstantinos Georgiou, Avner Magen, Iannis Tourlakis
2007 J jnl
Dimensionality Reductions in
Discret. Comput. Geom.
Avner Magen
2007 — conf
Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to
APPROX-RANDOM
Hamed Hatami, Avner Magen, Evangelos Markakis
2007 A* conf
Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy.
FOCS
Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis
2006 Misc conf
A Rigorous Analysis for Set-Up Time Models - A Metric Perspective.
COCOON
Eitan Bachmat, Tao-Kai Lam, Avner Magen
2006 J jnl
Integrality gaps of semidefinite programs for Vertex Cover and relations to ℓ
CoRR
Hamed Hatami, Avner Magen, Vangelis Markakis
2006 — conf
Monotone Circuits for the Majority Function.
APPROX-RANDOM
Shlomo Hoory, Avner Magen, Toniann Pitassi
2006 J jnl
Rank Bounds and Integrality Gaps for Cutting Planes Procedures.
Theory Comput.
Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi
2006 J jnl
Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy.
Electron. Colloquium Comput. Complex.
Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis
2005 J jnl
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time.
SIAM J. Comput.
Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler
2005 A* conf
How Well Can Primal-Dual and Local-Ratio Algorithms Perform?.
ICALP
Allan Borodin, David Cashman, Avner Magen
2005 Misc conf
On-Line Algorithms for Market Equilibria.
COCOON
Spyros Angelopoulos, Atish Das Sarma, Avner Magen, Anastasios Viglas
2005 J jnl
Simple permutations mix well.
Theor. Comput. Sci.
Shlomo Hoory, Avner Magen, Steven A. Myers, Charles Rackoff
2005 — conf
Sublinear Geometric Algorithms.
Sublinear Algorithms
Bernard Chazelle, Ding Liu, Avner Magen
2005 J jnl
Sublinear Geometric Algorithms.
SIAM J. Comput.
Bernard Chazelle, Ding Liu, Avner Magen
2005 A conf
Toward a Model for Backtracking and Dynamic Programming.
CCC
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
2004 — conf
Approximate range searching in higher dimension.
CCCG
Ding Liu, Bernard Chazelle, Avner Magen
2004 J jnl
Metric Embeddings--Beyond One-Dimensional Distortion.
Discret. Comput. Geom.
Robert Krauthgamer, Nathan Linial, Avner Magen
2004 A* conf
Simple Permutations Mix Well.
ICALP
Shlomo Hoory, Avner Magen, Steven A. Myers, Charles Rackoff
2003 A* conf
A sublinear algorithm for weakly approximating edit distance.
STOC
Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami
2003 A* conf
Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua.
FOCS
Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi
2003 A* conf
Sublinear geometric algorithms.
STOC
Bernard Chazelle, Ding Liu, Avner Magen
2003 A* conf
Sublinear-time approximation of Euclidean minimum spanning tree.
SODA
Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler
2002 — conf
Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic Applications.
RANDOM
Avner Magen
2002 A* conf
Girth and euclidean distortion.
STOC
Nathan Linial, Avner Magen, Assaf Naor
2001 — —
On the Euclidicity of metric spaces.
Avner Magen
2000 J jnl
Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders.
J. Comb. Theory B
Nathan Linial, Avner Magen
1998 A* conf
Trees and Euclidean Metrics.
STOC
Nathan Linial, Avner Magen, Michael E. Saks