Search results for "Avner Magen"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
1	Allan Borodin, David Cashman, Avner Magen	How well can primal-dual and local-ratio algorithms perform?	ACM Transactions on Algorithms	2011	DBLP DOI BibTeX RDF
1	Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi	Toward a Model for Backtracking and Dynamic Programming.	Computational Complexity	2011	DBLP DOI BibTeX RDF
1	Avner Magen, Anastasios Zouzias	Low Rank Matrix-valued Chernoff Bounds and Approximate Matrix Multiplication.	SODA	2011	DBLP BibTeX RDF
1	Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou, Avner Magen	Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy.	FSTTCS	2011	DBLP DOI BibTeX RDF
1	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.	Electronic Colloquium on Computational Complexity (ECCC)	2010	DBLP BibTeX RDF
1	Avner Magen, Anastasios Zouzias	Low Rank Matrix-Valued Chernoff Bounds and Applications	CoRR	2010	DBLP BibTeX RDF
1	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.	2010	DBLP DOI BibTeX RDF
1	Per Austrin, Siavosh Benabbas, Avner Magen	On Quadratic Threshold CSPs.	LATIN	2010	DBLP DOI BibTeX RDF
1	Siavosh Benabbas, Avner Magen	Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain.	IPCO	2010	DBLP DOI BibTeX RDF
1	Piotr Indyk, Avner Magen, Anastasios Sidiropoulos, Anastasios Zouzias	Online Embeddings.	APPROX-RANDOM	2010	DBLP DOI BibTeX RDF
1	Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen	Toward a Model for Backtracking and Dynamic Programming.	Electronic Colloquium on Computational Complexity (ECCC)	2009	DBLP BibTeX RDF
1	Konstantinos Georgiou, Avner Magen, Madhur Tulsiani	Optimal Sherali-Adams Gaps from Pairwise Independence.	Electronic Colloquium on Computational Complexity (ECCC)	2009	DBLP BibTeX RDF
1	Avner Magen, Mohammad Moharrami	Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
1	Konstantinos Georgiou, Avner Magen, Madhur Tulsiani	Optimal Sherali-Adams Gaps from Pairwise Independence.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
1	Konstantinos Georgiou, Avner Magen, Iannis Tourlakis	On the Tightening of the Standard SDP for Vertex Cover with $ell_1$ Inequalities.	FSTTCS	2009	DBLP DOI BibTeX RDF
1	Eitan Bachmat, Tao-Kai Lam, Avner Magen	Analysis of set-up time models: A metric perspective.	Theor. Comput. Sci.	2008	DBLP DOI BibTeX RDF
1	Hamed Hatami, Avner Magen, Evangelos Markakis	Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to l1 Embeddability of Negative Type Metrics.	SIAM J. Discrete Math.	2008	DBLP DOI BibTeX RDF
1	Bernard Chazelle, Ding Liu, Avner Magen	Approximate range searching in higher dimension.	Comput. Geom.	2008	DBLP DOI BibTeX RDF
1	Mohammad Moharrami, Avner Magen	On the nonexistence of dimension reduction for $\ell2_2$ metrics.	CCCG	2008	DBLP BibTeX RDF
1	Konstantinos Georgiou, Avner Magen, Iannis Tourlakis	Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities.	IPCO	2008	DBLP DOI BibTeX RDF
1	Avner Magen, Anastasios Zouzias	Near Optimal Dimensionality Reductions That Preserve Volumes.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
1	Avner Magen	Dimensionality Reductions in l2 that Preserve Volumes and Distance to Affine Spaces.	Discrete & Computational Geometry	2007	DBLP DOI BibTeX RDF
1	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	DBLP DOI BibTeX RDF
1	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	DBLP DOI BibTeX RDF
1	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)	2006	DBLP BibTeX RDF
1	Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi	Rank Bounds and Integrality Gaps for Cutting Planes Procedures.	Theory of Computing	2006	DBLP DOI BibTeX RDF
1	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	2006	DBLP BibTeX RDF
1	Eitan Bachmat, Tao-Kai Lam, Avner Magen	A Rigorous Analysis for Set-Up Time Models - A Metric Perspective.	COCOON	2006	DBLP DOI BibTeX RDF
1	Shlomo Hoory, Avner Magen, Toniann Pitassi	Monotone Circuits for the Majority Function.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
1	Shlomo Hoory, Avner Magen, Steven Myers, Charles Rackoff	Simple permutations mix well.	Theor. Comput. Sci.	2005	DBLP DOI BibTeX RDF
1	Bernard Chazelle, Ding Liu, Avner Magen	Sublinear Geometric Algorithms.	SIAM J. Comput.	2005	DBLP DOI BibTeX RDF
1	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.	2005	DBLP DOI BibTeX RDF
1	Allan Borodin, David Cashman, Avner Magen	How Well Can Primal-Dual and Local-Ratio Algorithms Perform?.	ICALP	2005	DBLP DOI BibTeX RDF
1	Bernard Chazelle, Ding Liu, Avner Magen	Sublinear Geometric Algorithms.	Sublinear Algorithms	2005	DBLP BibTeX RDF
1	Spyros Angelopoulos, Atish Das Sarma, Avner Magen, Anastasios Viglas	On-Line Algorithms for Market Equilibria.	COCOON	2005	DBLP DOI BibTeX RDF
1	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	DBLP DOI BibTeX RDF
1	Robert Krauthgamer, Nathan Linial, Avner Magen	Metric Embeddings--Beyond One-Dimensional Distortion.	Discrete & Computational Geometry	2004	DBLP DOI BibTeX RDF
1	Shlomo Hoory, Avner Magen, Steven Myers, Charles Rackoff	Simple Permutations Mix Well.	ICALP	2004	DBLP DOI BibTeX RDF
1	Ding Liu, Bernard Chazelle, Avner Magen	Approximate range searching in higher dimension.	CCCG	2004	DBLP BibTeX RDF
1	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	DBLP DOI BibTeX RDF
1	Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi	Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua.	FOCS	2003	DBLP DOI BibTeX RDF
1	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	DBLP DOI BibTeX RDF	approximation, string matching, sublinear algorithms
1	Bernard Chazelle, Ding Liu, Avner Magen	Sublinear geometric algorithms.	STOC	2003	DBLP DOI BibTeX RDF	approximate shortest paths, polyhedral intersection, sublinear algorithms
1	Avner Magen	Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic Applications.	RANDOM	2002	DBLP DOI BibTeX RDF
1	Nathan Linial, Avner Magen, Assaf Naor	Girth and euclidean distortion.	STOC	2002	DBLP DOI BibTeX RDF	EUCLID
1	Nathan Linial, Avner Magen	Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders.	J. Comb. Theory, Ser. B	2000	DBLP DOI BibTeX RDF
1	Nathan Linial, Avner Magen, Michael E. Saks	Trees and Euclidean Metrics.	STOC	1998	DBLP DOI BibTeX RDF

Publications of "Avner Magen" ( http://dblp.L3S.de/Authors/Avner_Magen )