Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Avner Magen
@article{DBLP:journals/dmtcs/AustrinBM12,
author = {Per Austrin and
Siavosh Benabbas and
Avner Magen},
title = {On Quadratic Threshold CSPs},
journal = {Discret. Math. Theor. Comput. Sci.},
volume = {14},
number = {2},
pages = {205--228},
year = {2012},
url = {https://doi.org/10.46298/dmtcs.591},
doi = {10.46298/DMTCS.591},
timestamp = {Tue, 24 Jan 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/dmtcs/AustrinBM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BenabbasGMT12,
author = {Siavosh Benabbas and
Konstantinos Georgiou and
Avner Magen and
Madhur Tulsiani},
title = {{SDP} Gaps from Pairwise Independence},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {269--289},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a012},
doi = {10.4086/TOC.2012.V008A012},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BenabbasGMT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/AlekhnovichBBIMP11,
author = {Michael Alekhnovich and
Allan Borodin and
Joshua Buresh{-}Oppenheim and
Russell Impagliazzo and
Avner Magen and
Toniann Pitassi},
title = {Toward a Model for Backtracking and Dynamic Programming},
journal = {Comput. Complex.},
volume = {20},
number = {4},
pages = {679--740},
year = {2011},
url = {https://doi.org/10.1007/s00037-011-0028-y},
doi = {10.1007/S00037-011-0028-Y},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/AlekhnovichBBIMP11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/talg/BorodinCM11,
author = {Allan Borodin and
David Cashman and
Avner Magen},
title = {How well can primal-dual and local-ratio algorithms perform?},
journal = {{ACM} Trans. Algorithms},
volume = {7},
number = {3},
pages = {29:1--29:26},
year = {2011},
url = {https://doi.org/10.1145/1978782.1978784},
doi = {10.1145/1978782.1978784},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/BorodinCM11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/BenabbasCGM11,
author = {Siavosh Benabbas and
Siu On Chan and
Konstantinos Georgiou and
Avner Magen},
editor = {Supratik Chakraborty and
Amit Kumar},
title = {Tight Gaps for Vertex Cover in the Sherali-Adams {SDP} Hierarchy},
booktitle = {{IARCS} Annual Conference on Foundations of Software Technology and
Theoretical Computer Science, {FSTTCS} 2011, December 12-14, 2011,
Mumbai, India},
series = {LIPIcs},
volume = {13},
pages = {41--54},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2011},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2011.41},
doi = {10.4230/LIPICS.FSTTCS.2011.41},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/fsttcs/BenabbasCGM11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/MagenZ11,
author = {Avner Magen and
Anastasios Zouzias},
editor = {Dana Randall},
title = {Low Rank Matrix-valued Chernoff Bounds and Approximate Matrix Multiplication},
booktitle = {Proceedings of the Twenty-Second Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2011, San Francisco, California, USA, January 23-25,
2011},
pages = {1422--1436},
publisher = {{SIAM}},
year = {2011},
url = {https://doi.org/10.1137/1.9781611973082.109},
doi = {10.1137/1.9781611973082.109},
timestamp = {Tue, 02 Feb 2021 17:07:23 +0100},
biburl = {https://dblp.org/rec/conf/soda/MagenZ11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/GeorgiouMPT10,
author = {Konstantinos Georgiou and
Avner Magen and
Toniann Pitassi and
Iannis Tourlakis},
title = {Integrality Gaps of 2-o(1) for Vertex Cover SDPs in the Lov[a-acute]sz--Schrijver
Hierarchy},
journal = {{SIAM} J. Comput.},
volume = {39},
number = {8},
pages = {3553--3570},
year = {2010},
url = {https://doi.org/10.1137/080721479},
doi = {10.1137/080721479},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/GeorgiouMPT10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/IndykMSZ10,
author = {Piotr Indyk and
Avner Magen and
Anastasios Sidiropoulos and
Anastasios Zouzias},
editor = {Maria J. Serna and
Ronen Shaltiel and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim},
title = {Online Embeddings},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 13th International Workshop, {APPROX} 2010, and 14th
International Workshop, {RANDOM} 2010, Barcelona, Spain, September
1-3, 2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6302},
pages = {246--259},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-15369-3\_19},
doi = {10.1007/978-3-642-15369-3\_19},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/IndykMSZ10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/BenabbasM10,
author = {Siavosh Benabbas and
Avner Magen},
editor = {Friedrich Eisenbrand and
F. Bruce Shepherd},
title = {Extending {SDP} Integrality Gaps to Sherali-Adams with Applications
to Quadratic Programming and MaxCutGain},
booktitle = {Integer Programming and Combinatorial Optimization, 14th International
Conference, {IPCO} 2010, Lausanne, Switzerland, June 9-11, 2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6080},
pages = {299--312},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-13036-6\_23},
doi = {10.1007/978-3-642-13036-6\_23},
timestamp = {Tue, 14 May 2019 10:00:50 +0200},
biburl = {https://dblp.org/rec/conf/ipco/BenabbasM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/latin/AustrinBM10,
author = {Per Austrin and
Siavosh Benabbas and
Avner Magen},
editor = {Alejandro L{\'{o}}pez{-}Ortiz},
title = {On Quadratic Threshold CSPs},
booktitle = {{LATIN} 2010: Theoretical Informatics, 9th Latin American Symposium,
Oaxaca, Mexico, April 19-23, 2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6034},
pages = {332--343},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-12200-2\_30},
doi = {10.1007/978-3-642-12200-2\_30},
timestamp = {Tue, 14 May 2019 10:00:53 +0200},
biburl = {https://dblp.org/rec/conf/latin/AustrinBM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1005-2724,
author = {Avner Magen and
Anastasios Zouzias},
title = {Low Rank Matrix-Valued Chernoff Bounds and Applications},
journal = {CoRR},
volume = {abs/1005.2724},
year = {2010},
url = {http://arxiv.org/abs/1005.2724},
eprinttype = {arXiv},
eprint = {1005.2724},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1005-2724.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BenabbasGM10,
author = {Siavosh Benabbas and
Konstantinos Georgiou and
Avner Magen},
title = {The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs
Fool Strong LPs and some Tight Integrality Gaps for SDPs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-169}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/169},
eprinttype = {ECCC},
eprint = {TR10-169},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BenabbasGM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/GeorgiouMT09,
author = {Konstantinos Georgiou and
Avner Magen and
Madhur Tulsiani},
editor = {Irit Dinur and
Klaus Jansen and
Joseph Naor and
Jos{\'{e}} D. P. Rolim},
title = {Optimal Sherali-Adams Gaps from Pairwise Independence},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 12th International Workshop, {APPROX} 2009, and 13th
International Workshop, {RANDOM} 2009, Berkeley, CA, USA, August 21-23,
2009. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5687},
pages = {125--139},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-03685-9\_10},
doi = {10.1007/978-3-642-03685-9\_10},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/GeorgiouMT09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/MagenM09,
author = {Avner Magen and
Mohammad Moharrami},
editor = {Irit Dinur and
Klaus Jansen and
Joseph Naor and
Jos{\'{e}} D. P. Rolim},
title = {Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams
Hierarchy},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 12th International Workshop, {APPROX} 2009, and 13th
International Workshop, {RANDOM} 2009, Berkeley, CA, USA, August 21-23,
2009. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5687},
pages = {258--271},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-03685-9\_20},
doi = {10.1007/978-3-642-03685-9\_20},
timestamp = {Tue, 23 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/MagenM09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/GeorgiouMT09,
author = {Konstantinos Georgiou and
Avner Magen and
Iannis Tourlakis},
editor = {Ravi Kannan and
K. Narayan Kumar},
title = {On the Tightening of the Standard {SDP} for Vertex Cover with {\textdollar}ell{\_}1{\textdollar}
Inequalities},
booktitle = {{IARCS} Annual Conference on Foundations of Software Technology and
Theoretical Computer Science, {FSTTCS} 2009, December 15-17, 2009,
{IIT} Kanpur, India},
series = {LIPIcs},
volume = {4},
pages = {203--214},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2009},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2319},
doi = {10.4230/LIPICS.FSTTCS.2009.2319},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/fsttcs/GeorgiouMT09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AlekhnovichBBIM09,
author = {Michael Alekhnovich and
Allan Borodin and
Joshua Buresh{-}Oppenheim and
Russell Impagliazzo and
Avner Magen},
title = {Toward a Model for Backtracking and Dynamic Programming},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR09-038}},
year = {2009},
url = {https://eccc.weizmann.ac.il/report/2009/038},
eprinttype = {ECCC},
eprint = {TR09-038},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AlekhnovichBBIM09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GeorgiouMT09,
author = {Konstantinos Georgiou and
Avner Magen and
Madhur Tulsiani},
title = {Optimal Sherali-Adams Gaps from Pairwise Independence},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR09-061}},
year = {2009},
url = {https://eccc.weizmann.ac.il/report/2009/061},
eprinttype = {ECCC},
eprint = {TR09-061},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GeorgiouMT09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/comgeo/ChazelleLM08,
author = {Bernard Chazelle and
Ding Liu and
Avner Magen},
title = {Approximate range searching in higher dimension},
journal = {Comput. Geom.},
volume = {39},
number = {1},
pages = {24--29},
year = {2008},
url = {https://doi.org/10.1016/j.comgeo.2007.05.008},
doi = {10.1016/J.COMGEO.2007.05.008},
timestamp = {Thu, 11 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/comgeo/ChazelleLM08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamdm/HatamiMM08,
author = {Hamed Hatami and
Avner Magen and
Evangelos Markakis},
title = {Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations
to l\({}_{\mbox{1}}\) Embeddability of Negative Type Metrics},
journal = {{SIAM} J. Discret. Math.},
volume = {23},
number = {1},
pages = {178--194},
year = {2008},
url = {https://doi.org/10.1137/070700103},
doi = {10.1137/070700103},
timestamp = {Sat, 25 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamdm/HatamiMM08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/BachmatLM08,
author = {Eitan Bachmat and
Tao{-}Kai Lam and
Avner Magen},
title = {Analysis of set-up time models: {A} metric perspective},
journal = {Theor. Comput. Sci.},
volume = {401},
number = {1-3},
pages = {172--180},
year = {2008},
url = {https://doi.org/10.1016/j.tcs.2008.04.021},
doi = {10.1016/J.TCS.2008.04.021},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/BachmatLM08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/MagenZ08,
author = {Avner Magen and
Anastasios Zouzias},
editor = {Ashish Goel and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Ronitt Rubinfeld},
title = {Near Optimal Dimensionality Reductions That Preserve Volumes},
booktitle = {Approximation, Randomization and Combinatorial Optimization. Algorithms
and Techniques, 11th International Workshop, {APPROX} 2008, and 12th
International Workshop, {RANDOM} 2008, Boston, MA, USA, August 25-27,
2008. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5171},
pages = {523--534},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-85363-3\_41},
doi = {10.1007/978-3-540-85363-3\_41},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/MagenZ08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cccg/MoharramiM08,
author = {Mohammad Moharrami and
Avner Magen},
title = {On the nonexistence of dimension reduction for {\(\mathscr{l}\)}2\({}_{\mbox{2}}\)
metrics},
booktitle = {Proceedings of the 20th Annual Canadian Conference on Computational
Geometry, Montr{\'{e}}al, Canada, August 13-15, 2008},
year = {2008},
timestamp = {Wed, 12 May 2021 14:19:37 +0200},
biburl = {https://dblp.org/rec/conf/cccg/MoharramiM08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/GeorgiouMT08,
author = {Konstantinos Georgiou and
Avner Magen and
Iannis Tourlakis},
editor = {Andrea Lodi and
Alessandro Panconesi and
Giovanni Rinaldi},
title = {Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities},
booktitle = {Integer Programming and Combinatorial Optimization, 13th International
Conference, {IPCO} 2008, Bertinoro, Italy, May 26-28, 2008, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5035},
pages = {140--153},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-68891-4\_10},
doi = {10.1007/978-3-540-68891-4\_10},
timestamp = {Tue, 14 May 2019 10:00:50 +0200},
biburl = {https://dblp.org/rec/conf/ipco/GeorgiouMT08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dcg/Magen07,
author = {Avner Magen},
title = {Dimensionality Reductions in \emph{l}\({}_{\mbox{2}}\) that Preserve
Volumes and Distance to Affine Spaces},
journal = {Discret. Comput. Geom.},
volume = {38},
number = {1},
pages = {139--153},
year = {2007},
url = {https://doi.org/10.1007/s00454-007-1329-4},
doi = {10.1007/S00454-007-1329-4},
timestamp = {Thu, 12 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/dcg/Magen07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/HatamiMM07,
author = {Hamed Hatami and
Avner Magen and
Evangelos Markakis},
editor = {Moses Charikar and
Klaus Jansen and
Omer Reingold and
Jos{\'{e}} D. P. Rolim},
title = {Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations
to \emph{l}\({}_{\mbox{1}}\) Embeddability of Negative Type Metrics},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 10th International Workshop, {APPROX} 2007, and 11th
International Workshop, {RANDOM} 2007, Princeton, NJ, USA, August
20-22, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4627},
pages = {164--179},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74208-1\_12},
doi = {10.1007/978-3-540-74208-1\_12},
timestamp = {Sat, 30 Sep 2023 09:34:32 +0200},
biburl = {https://dblp.org/rec/conf/approx/HatamiMM07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GeorgiouMPT07,
author = {Konstantinos Georgiou and
Avner Magen and
Toniann Pitassi and
Iannis Tourlakis},
title = {Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lov{\'{e}}sz-Schrijver
Hierarchy},
booktitle = {48th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2007), October 20-23, 2007, Providence, RI, USA, Proceedings},
pages = {702--712},
publisher = {{IEEE} Computer Society},
year = {2007},
url = {https://doi.org/10.1109/FOCS.2007.35},
doi = {10.1109/FOCS.2007.35},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GeorgiouMPT07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Buresh-OppenheimGHMP06,
author = {Joshua Buresh{-}Oppenheim and
Nicola Galesi and
Shlomo Hoory and
Avner Magen and
Toniann Pitassi},
title = {Rank Bounds and Integrality Gaps for Cutting Planes Procedures},
journal = {Theory Comput.},
volume = {2},
number = {4},
pages = {65--90},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a004},
doi = {10.4086/TOC.2006.V002A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Buresh-OppenheimGHMP06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/HooryMP06,
author = {Shlomo Hoory and
Avner Magen and
Toniann Pitassi},
editor = {Josep D{\'{\i}}az and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Uri Zwick},
title = {Monotone Circuits for the Majority Function},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 9th International Workshop on Approximation Algorithms
for Combinatorial Optimization Problems, {APPROX} 2006 and 10th International
Workshop on Randomization and Computation, {RANDOM} 2006, Barcelona,
Spain, August 28-30 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4110},
pages = {410--425},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11830924\_38},
doi = {10.1007/11830924\_38},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/HooryMP06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/BachmatLM06,
author = {Eitan Bachmat and
Tao{-}Kai Lam and
Avner Magen},
editor = {Danny Z. Chen and
D. T. Lee},
title = {A Rigorous Analysis for Set-Up Time Models - {A} Metric Perspective},
booktitle = {Computing and Combinatorics, 12th Annual International Conference,
{COCOON} 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4112},
pages = {387--397},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11809678\_41},
doi = {10.1007/11809678\_41},
timestamp = {Tue, 14 May 2019 10:00:35 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/BachmatLM06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-cs-0601011,
author = {Hamed Hatami and
Avner Magen and
Vangelis Markakis},
title = {Integrality gaps of semidefinite programs for Vertex Cover and relations
to {\(\mathscr{l}\)}\({}_{\mbox{1}}\) embeddability of Negative Type
metrics},
journal = {CoRR},
volume = {abs/cs/0601011},
year = {2006},
url = {http://arxiv.org/abs/cs/0601011},
eprinttype = {arXiv},
eprint = {cs/0601011},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-cs-0601011.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GeorgiouMPT06,
author = {Konstantinos Georgiou and
Avner Magen and
Toniann Pitassi and
Iannis Tourlakis},
title = {Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver
hierarchy},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR06-152}},
year = {2006},
url = {https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-152/index.html},
eprinttype = {ECCC},
eprint = {TR06-152},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GeorgiouMPT06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CzumajEFMNRS05,
author = {Artur Czumaj and
Funda Erg{\"{u}}n and
Lance Fortnow and
Avner Magen and
Ilan Newman and
Ronitt Rubinfeld and
Christian Sohler},
title = {Approximating the Weight of the Euclidean Minimum Spanning Tree in
Sublinear Time},
journal = {{SIAM} J. Comput.},
volume = {35},
number = {1},
pages = {91--109},
year = {2005},
url = {https://doi.org/10.1137/S0097539703435297},
doi = {10.1137/S0097539703435297},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CzumajEFMNRS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ChazelleLM05,
author = {Bernard Chazelle and
Ding Liu and
Avner Magen},
title = {Sublinear Geometric Algorithms},
journal = {{SIAM} J. Comput.},
volume = {35},
number = {3},
pages = {627--646},
year = {2005},
url = {https://doi.org/10.1137/S009753970444572X},
doi = {10.1137/S009753970444572X},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ChazelleLM05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/HooryMMR05,
author = {Shlomo Hoory and
Avner Magen and
Steven A. Myers and
Charles Rackoff},
title = {Simple permutations mix well},
journal = {Theor. Comput. Sci.},
volume = {348},
number = {2-3},
pages = {251--261},
year = {2005},
url = {https://doi.org/10.1016/j.tcs.2005.09.016},
doi = {10.1016/J.TCS.2005.09.016},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/HooryMMR05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/AlekhnovichBBIMP05,
author = {Michael Alekhnovich and
Allan Borodin and
Joshua Buresh{-}Oppenheim and
Russell Impagliazzo and
Avner Magen and
Toniann Pitassi},
title = {Toward a Model for Backtracking and Dynamic Programming},
booktitle = {20th Annual {IEEE} Conference on Computational Complexity {(CCC} 2005),
11-15 June 2005, San Jose, CA, {USA}},
pages = {308--322},
publisher = {{IEEE} Computer Society},
year = {2005},
url = {https://doi.org/10.1109/CCC.2005.32},
doi = {10.1109/CCC.2005.32},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/AlekhnovichBBIMP05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/AngelopoulosSMV05,
author = {Spyros Angelopoulos and
Atish Das Sarma and
Avner Magen and
Anastasios Viglas},
editor = {Lusheng Wang},
title = {On-Line Algorithms for Market Equilibria},
booktitle = {Computing and Combinatorics, 11th Annual International Conference,
{COCOON} 2005, Kunming, China, August 16-29, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3595},
pages = {596--607},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/11533719\_61},
doi = {10.1007/11533719\_61},
timestamp = {Tue, 14 May 2019 10:00:35 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/AngelopoulosSMV05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/BorodinCM05,
author = {Allan Borodin and
David Cashman and
Avner Magen},
editor = {Lu{\'{\i}}s Caires and
Giuseppe F. Italiano and
Lu{\'{\i}}s Monteiro and
Catuscia Palamidessi and
Moti Yung},
title = {How Well Can Primal-Dual and Local-Ratio Algorithms Perform?},
booktitle = {Automata, Languages and Programming, 32nd International Colloquium,
{ICALP} 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3580},
pages = {943--955},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/11523468\_76},
doi = {10.1007/11523468\_76},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/BorodinCM05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dagstuhl/ChazelleLM05,
author = {Bernard Chazelle and
Ding Liu and
Avner Magen},
editor = {Artur Czumaj and
S. Muthu Muthukrishnan and
Ronitt Rubinfeld and
Christian Sohler},
title = {Sublinear Geometric Algorithms},
booktitle = {Sublinear Algorithms, 17.07. - 22.07.2005},
series = {Dagstuhl Seminar Proceedings},
volume = {05291},
publisher = {Internationales Begegnungs- und Forschungszentrum f{\"{u}}r Informatik
(IBFI), Schloss Dagstuhl, Germany},
year = {2005},
url = {http://drops.dagstuhl.de/opus/volltexte/2006/554},
timestamp = {Mon, 26 Jun 2023 20:44:05 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/ChazelleLM05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dcg/KrauthgamerLM04,
author = {Robert Krauthgamer and
Nathan Linial and
Avner Magen},
title = {Metric Embeddings--Beyond One-Dimensional Distortion},
journal = {Discret. Comput. Geom.},
volume = {31},
number = {3},
pages = {339--356},
year = {2004},
url = {https://doi.org/10.1007/s00454-003-2872-2},
doi = {10.1007/S00454-003-2872-2},
timestamp = {Thu, 12 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/dcg/KrauthgamerLM04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cccg/LiuCM04,
author = {Ding Liu and
Bernard Chazelle and
Avner Magen},
title = {Approximate range searching in higher dimension},
booktitle = {Proceedings of the 16th Canadian Conference on Computational Geometry,
CCCG'04, Concordia University, Montr{\'{e}}al, Qu{\'{e}}bec,
Canada, August 9-11, 2004},
pages = {154--157},
year = {2004},
url = {http://www.cccg.ca/proceedings/2004/23.pdf},
timestamp = {Wed, 12 May 2021 14:19:37 +0200},
biburl = {https://dblp.org/rec/conf/cccg/LiuCM04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/HooryMMR04,
author = {Shlomo Hoory and
Avner Magen and
Steven A. Myers and
Charles Rackoff},
editor = {Josep D{\'{\i}}az and
Juhani Karhum{\"{a}}ki and
Arto Lepist{\"{o}} and
Donald Sannella},
title = {Simple Permutations Mix Well},
booktitle = {Automata, Languages and Programming: 31st International Colloquium,
{ICALP} 2004, Turku, Finland, July 12-16, 2004. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3142},
pages = {770--781},
publisher = {Springer},
year = {2004},
url = {https://doi.org/10.1007/978-3-540-27836-8\_65},
doi = {10.1007/978-3-540-27836-8\_65},
timestamp = {Tue, 28 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/HooryMMR04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Buresh-OppenheimGHMP03,
author = {Josh Buresh{-}Oppenheim and
Nicola Galesi and
Shlomo Hoory and
Avner Magen and
Toniann Pitassi},
title = {Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua},
booktitle = {44th Symposium on Foundations of Computer Science {(FOCS} 2003), 11-14
October 2003, Cambridge, MA, USA, Proceedings},
pages = {318--327},
publisher = {{IEEE} Computer Society},
year = {2003},
url = {https://doi.org/10.1109/SFCS.2003.1238206},
doi = {10.1109/SFCS.2003.1238206},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Buresh-OppenheimGHMP03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CzumajEFMNRS03,
author = {Artur Czumaj and
Funda Erg{\"{u}}n and
Lance Fortnow and
Avner Magen and
Ilan Newman and
Ronitt Rubinfeld and
Christian Sohler},
title = {Sublinear-time approximation of Euclidean minimum spanning tree},
booktitle = {Proceedings of the Fourteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, January 12-14, 2003, Baltimore, Maryland, {USA}},
pages = {813--822},
publisher = {{ACM/SIAM}},
year = {2003},
url = {http://dl.acm.org/citation.cfm?id=644108.644242},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/CzumajEFMNRS03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BatuEKMRRS03,
author = {Tugkan Batu and
Funda Erg{\"{u}}n and
Joe Kilian and
Avner Magen and
Sofya Raskhodnikova and
Ronitt Rubinfeld and
Rahul Sami},
editor = {Lawrence L. Larmore and
Michel X. Goemans},
title = {A sublinear algorithm for weakly approximating edit distance},
booktitle = {Proceedings of the 35th Annual {ACM} Symposium on Theory of Computing,
June 9-11, 2003, San Diego, CA, {USA}},
pages = {316--324},
publisher = {{ACM}},
year = {2003},
url = {https://doi.org/10.1145/780542.780590},
doi = {10.1145/780542.780590},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BatuEKMRRS03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChazelleLM03,
author = {Bernard Chazelle and
Ding Liu and
Avner Magen},
editor = {Lawrence L. Larmore and
Michel X. Goemans},
title = {Sublinear geometric algorithms},
booktitle = {Proceedings of the 35th Annual {ACM} Symposium on Theory of Computing,
June 9-11, 2003, San Diego, CA, {USA}},
pages = {531--540},
publisher = {{ACM}},
year = {2003},
url = {https://doi.org/10.1145/780542.780620},
doi = {10.1145/780542.780620},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChazelleLM03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/random/Magen02,
author = {Avner Magen},
editor = {Jos{\'{e}} D. P. Rolim and
Salil P. Vadhan},
title = {Dimensionality Reductions That Preserve Volumes and Distance to Affine
Spaces, and Their Algorithmic Applications},
booktitle = {Randomization and Approximation Techniques, 6th International Workshop,
{RANDOM} 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2483},
pages = {239--253},
publisher = {Springer},
year = {2002},
url = {https://doi.org/10.1007/3-540-45726-7\_19},
doi = {10.1007/3-540-45726-7\_19},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/random/Magen02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LinialMN02,
author = {Nathan Linial and
Avner Magen and
Assaf Naor},
editor = {John H. Reif},
title = {Girth and euclidean distortion},
booktitle = {Proceedings on 34th Annual {ACM} Symposium on Theory of Computing,
May 19-21, 2002, Montr{\'{e}}al, Qu{\'{e}}bec, Canada},
pages = {705--711},
publisher = {{ACM}},
year = {2002},
url = {https://doi.org/10.1145/509907.510009},
doi = {10.1145/509907.510009},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/LinialMN02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@phdthesis{DBLP:phd/il/Magen01,
author = {Avner Magen},
title = {On the Euclidicity of metric spaces},
school = {Hebrew University of Jerusalem, Israel},
year = {2001},
url = {https://huji-primo.hosted.exlibrisgroup.com/permalink/f/13ns5ae/972HUJI\_ALMA21159933550003701},
timestamp = {Wed, 14 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/phd/il/Magen01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jct/LinialM00,
author = {Nathan Linial and
Avner Magen},
title = {Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles
and Expanders},
journal = {J. Comb. Theory, Ser. {B}},
volume = {79},
number = {2},
pages = {157--171},
year = {2000},
url = {https://doi.org/10.1006/jctb.2000.1953},
doi = {10.1006/JCTB.2000.1953},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jct/LinialM00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LinialMS98,
author = {Nathan Linial and
Avner Magen and
Michael E. Saks},
editor = {Jeffrey Scott Vitter},
title = {Trees and Euclidean Metrics},
booktitle = {Proceedings of the Thirtieth Annual {ACM} Symposium on the Theory
of Computing, Dallas, Texas, USA, May 23-26, 1998},
pages = {169--175},
publisher = {{ACM}},
year = {1998},
url = {https://doi.org/10.1145/276698.276726},
doi = {10.1145/276698.276726},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/LinialMS98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-04-21 17:32 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
