Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSearch dblp for Publications
export results for "toc:db/conf/stoc/stoc2009.bht:"
download as .bib file
@inproceedings{DBLP:conf/stoc/AharonovALV09,
author = {Dorit Aharonov and
Itai Arad and
Zeph Landau and
Umesh V. Vazirani},
editor = {Michael Mitzenmacher},
title = {The detectability lemma and quantum gap amplification},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {417--426},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536472},
doi = {10.1145/1536414.1536472},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AharonovALV09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AndersenP09,
author = {Reid Andersen and
Yuval Peres},
editor = {Michael Mitzenmacher},
title = {Finding sparse cuts locally using evolving sets},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {235--244},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536449},
doi = {10.1145/1536414.1536449},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AndersenP09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AndoniO09,
author = {Alexandr Andoni and
Krzysztof Onak},
editor = {Michael Mitzenmacher},
title = {Approximating edit distance in near-linear time},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {199--204},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536444},
doi = {10.1145/1536414.1536444},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AndoniO09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AronovES09,
author = {Boris Aronov and
Esther Ezra and
Micha Sharir},
editor = {Michael Mitzenmacher},
title = {Small-size epsilon-nets for axis-parallel rectangles and boxes},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {639--648},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536501},
doi = {10.1145/1536414.1536501},
timestamp = {Wed, 25 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/AronovES09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AroraDS09,
author = {Sanjeev Arora and
Constantinos Daskalakis and
David Steurer},
editor = {Michael Mitzenmacher},
title = {Message passing algorithms and improved {LP} decoding},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {3--12},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536418},
doi = {10.1145/1536414.1536418},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AroraDS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AustrinH09,
author = {Per Austrin and
Johan H{\aa}stad},
editor = {Michael Mitzenmacher},
title = {Randomly supported independence and resistance},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {483--492},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536481},
doi = {10.1145/1536414.1536481},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AustrinH09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AzarGY09,
author = {Yossi Azar and
Iftah Gamzu and
Xiaoxin Yin},
editor = {Michael Mitzenmacher},
title = {Multiple intents re-ranking},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {669--678},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536505},
doi = {10.1145/1536414.1536505},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AzarGY09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BabaiBS09,
author = {L{\'{a}}szl{\'{o}} Babai and
Robert Beals and
{\'{A}}kos Seress},
editor = {Michael Mitzenmacher},
title = {Polynomial-time theory of matrix groups},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {55--64},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536425},
doi = {10.1145/1536414.1536425},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BabaiBS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BarenboimE09,
author = {Leonid Barenboim and
Michael Elkin},
editor = {Michael Mitzenmacher},
title = {Distributed (delta+1)-coloring in linear (in delta) time},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {111--120},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536432},
doi = {10.1145/1536414.1536432},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BarenboimE09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BateniCG09,
author = {MohammadHossein Bateni and
Moses Charikar and
Venkatesan Guruswami},
editor = {Michael Mitzenmacher},
title = {MaxMin allocation via degree lower-bounded arborescences},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {543--552},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536488},
doi = {10.1145/1536414.1536488},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BateniCG09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BatsonSS09,
author = {Joshua D. Batson and
Daniel A. Spielman and
Nikhil Srivastava},
editor = {Michael Mitzenmacher},
title = {Twice-ramanujan sparsifiers},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {255--262},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536451},
doi = {10.1145/1536414.1536451},
timestamp = {Sun, 25 Oct 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BatsonSS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Ben-SassonK09,
author = {Eli Ben{-}Sasson and
Swastik Kopparty},
editor = {Michael Mitzenmacher},
title = {Affine dispersers from subspace polynomials},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {65--74},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536426},
doi = {10.1145/1536414.1536426},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Ben-SassonK09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BernsteinK09,
author = {Aaron Bernstein and
David R. Karger},
editor = {Michael Mitzenmacher},
title = {A nearly optimal oracle for avoiding failed vertices and edges},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {101--110},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536431},
doi = {10.1145/1536414.1536431},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BernsteinK09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Blais09,
author = {Eric Blais},
editor = {Michael Mitzenmacher},
title = {Testing juntas nearly optimally},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {151--158},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536437},
doi = {10.1145/1536414.1536437},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Blais09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CaiLX09,
author = {Jin{-}yi Cai and
Pinyan Lu and
Mingji Xia},
editor = {Michael Mitzenmacher},
title = {Holant problems and counting {CSP}},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {715--724},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536511},
doi = {10.1145/1536414.1536511},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/CaiLX09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CardinalFJJM09,
author = {Jean Cardinal and
Samuel Fiorini and
Gwena{\"{e}}l Joret and
Rapha{\"{e}}l M. Jungers and
J. Ian Munro},
editor = {Michael Mitzenmacher},
title = {An efficient algorithm for partial order production},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {93--100},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536430},
doi = {10.1145/1536414.1536430},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/CardinalFJJM09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChadhaGKM09,
author = {Jivitej S. Chadha and
Naveen Garg and
Amit Kumar and
V. N. Muralidhara},
editor = {Michael Mitzenmacher},
title = {A competitive algorithm for minimizing weighted flow time on unrelatedmachines
with speed augmentation},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {679--684},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536506},
doi = {10.1145/1536414.1536506},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChadhaGKM09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChalopinG09,
author = {J{\'{e}}r{\'{e}}mie Chalopin and
Daniel Gon{\c{c}}alves},
editor = {Michael Mitzenmacher},
title = {Every planar graph is the intersection graph of segments in the plane:
extended abstract},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {631--638},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536500},
doi = {10.1145/1536414.1536500},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChalopinG09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChambersEN09,
author = {Erin W. Chambers and
Jeff Erickson and
Amir Nayyeri},
editor = {Michael Mitzenmacher},
title = {Homology flows, cohomology cuts},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {273--282},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536453},
doi = {10.1145/1536414.1536453},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChambersEN09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CharikarMM09,
author = {Moses Charikar and
Konstantin Makarychev and
Yury Makarychev},
editor = {Michael Mitzenmacher},
title = {Integrality gaps for Sherali-Adams relaxations},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {283--292},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536455},
doi = {10.1145/1536414.1536455},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/CharikarMM09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChechikLPR09,
author = {Shiri Chechik and
Michael Langberg and
David Peleg and
Liam Roditty},
editor = {Michael Mitzenmacher},
title = {Fault-tolerant spanners for general graphs},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {435--444},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536475},
doi = {10.1145/1536414.1536475},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChechikLPR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenM09,
author = {Jing Chen and
Silvio Micali},
editor = {Michael Mitzenmacher},
title = {A new approach to auctions and resilient mechanism design},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {503--512},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536484},
doi = {10.1145/1536414.1536484},
timestamp = {Fri, 02 Aug 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenM09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChengW09,
author = {Qi Cheng and
Daqing Wan},
editor = {Michael Mitzenmacher},
title = {A deterministic reduction for the gap minimum distance problem: [extended
abstract]},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {33--38},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536421},
doi = {10.1145/1536414.1536421},
timestamp = {Tue, 18 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChengW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ClarksonW09,
author = {Kenneth L. Clarkson and
David P. Woodruff},
editor = {Michael Mitzenmacher},
title = {Numerical linear algebra in the streaming model},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {205--214},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536445},
doi = {10.1145/1536414.1536445},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ClarksonW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CleveGMSY09,
author = {Richard Cleve and
Daniel Gottesman and
Michele Mosca and
Rolando D. Somma and
David L. Yonge{-}Mallo},
editor = {Michael Mitzenmacher},
title = {Efficient discrete-time simulations of continuous-time quantum query
algorithms},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {409--416},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536471},
doi = {10.1145/1536414.1536471},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/CleveGMSY09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DaskalakisP09,
author = {Constantinos Daskalakis and
Christos H. Papadimitriou},
editor = {Michael Mitzenmacher},
title = {On oblivious PTAS's for nash equilibrium},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {75--84},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536427},
doi = {10.1145/1536414.1536427},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DaskalakisP09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DietzfelbingerW09,
author = {Martin Dietzfelbinger and
Philipp Woelfel},
editor = {Michael Mitzenmacher},
title = {Tight lower bounds for greedy routing in uniform small world rings},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {591--600},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536494},
doi = {10.1145/1536414.1536494},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DietzfelbingerW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DodisKL09,
author = {Yevgeniy Dodis and
Yael Tauman Kalai and
Shachar Lovett},
editor = {Michael Mitzenmacher},
title = {On cryptography with auxiliary input},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {621--630},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536498},
doi = {10.1145/1536414.1536498},
timestamp = {Mon, 15 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/DodisKL09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DodisW09,
author = {Yevgeniy Dodis and
Daniel Wichs},
editor = {Michael Mitzenmacher},
title = {Non-malleable extractors and symmetric key cryptography from weak
secrets},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {601--610},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536496},
doi = {10.1145/1536414.1536496},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DodisW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DworkL09,
author = {Cynthia Dwork and
Jing Lei},
editor = {Michael Mitzenmacher},
title = {Differential privacy and robust statistics},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {371--380},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536466},
doi = {10.1145/1536414.1536466},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DworkL09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DworkNRRV09,
author = {Cynthia Dwork and
Moni Naor and
Omer Reingold and
Guy N. Rothblum and
Salil P. Vadhan},
editor = {Michael Mitzenmacher},
title = {On the complexity of differentially private data release: efficient
algorithms and hardness results},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {381--390},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536467},
doi = {10.1145/1536414.1536467},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DworkNRRV09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Efremenko09,
author = {Klim Efremenko},
editor = {Michael Mitzenmacher},
title = {3-query locally decodable codes of subexponential length},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {39--44},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536422},
doi = {10.1145/1536414.1536422},
timestamp = {Mon, 16 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/Efremenko09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Even-DarMN09,
author = {Eyal Even{-}Dar and
Yishay Mansour and
Uri Nadav},
editor = {Michael Mitzenmacher},
title = {On the convergence of regret minimization dynamics in concave games},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {523--532},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536486},
doi = {10.1145/1536414.1536486},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Even-DarMN09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/FeldmanFKN09,
author = {Dan Feldman and
Amos Fiat and
Haim Kaplan and
Kobbi Nissim},
editor = {Michael Mitzenmacher},
title = {Private coresets},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {361--370},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536465},
doi = {10.1145/1536414.1536465},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/FeldmanFKN09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/FriedrichS09,
author = {Tobias Friedrich and
Thomas Sauerwald},
editor = {Michael Mitzenmacher},
title = {Near-perfect load balancing by randomized rounding},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {121--130},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536433},
doi = {10.1145/1536414.1536433},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/FriedrichS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Gafni09,
author = {Eli Gafni},
editor = {Michael Mitzenmacher},
title = {The extended BG-simulation and the characterization of t-resiliency},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {85--92},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536428},
doi = {10.1145/1536414.1536428},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Gafni09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Gentry09,
author = {Craig Gentry},
editor = {Michael Mitzenmacher},
title = {Fully homomorphic encryption using ideal lattices},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {169--178},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536440},
doi = {10.1145/1536414.1536440},
timestamp = {Mon, 26 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Gentry09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GhoshRS09,
author = {Arpita Ghosh and
Tim Roughgarden and
Mukund Sundararajan},
editor = {Michael Mitzenmacher},
title = {Universally utility-maximizing privacy mechanisms},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {351--360},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536464},
doi = {10.1145/1536414.1536464},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GhoshRS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GoldreichR09,
author = {Oded Goldreich and
Dana Ron},
editor = {Michael Mitzenmacher},
title = {On proximity oblivious testing},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {141--150},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536436},
doi = {10.1145/1536414.1536436},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GoldreichR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Goldwasser09,
author = {Shafi Goldwasser},
editor = {Michael Mitzenmacher},
title = {Athena lecture: Controlling Access to Programs?},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {167--168},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536416},
doi = {10.1145/1536414.1536416},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Goldwasser09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GopalanGR09,
author = {Parikshit Gopalan and
Venkatesan Guruswami and
Prasad Raghavendra},
editor = {Michael Mitzenmacher},
title = {List decoding tensor products and interleaved codes},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {13--22},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536419},
doi = {10.1145/1536414.1536419},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GopalanGR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GuptaK09,
author = {Anupam Gupta and
Amit Kumar},
editor = {Michael Mitzenmacher},
title = {A constant-factor approximation for stochastic Steiner forest},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {659--668},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536504},
doi = {10.1145/1536414.1536504},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/GuptaK09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GuptaKR09,
author = {Anupam Gupta and
Ravishankar Krishnaswamy and
R. Ravi},
editor = {Michael Mitzenmacher},
title = {Online and stochastic survivable network design},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {685--694},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536507},
doi = {10.1145/1536414.1536507},
timestamp = {Wed, 18 Aug 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/GuptaKR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Guruswami09,
author = {Venkatesan Guruswami},
editor = {Michael Mitzenmacher},
title = {Artin automorphisms, cyclotomic function fields, and folded list-decodable
codes},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {23--32},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536420},
doi = {10.1145/1536414.1536420},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Guruswami09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HaitnerRVW09,
author = {Iftach Haitner and
Omer Reingold and
Salil P. Vadhan and
Hoeteck Wee},
editor = {Michael Mitzenmacher},
title = {Inaccessible entropy},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {611--620},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536497},
doi = {10.1145/1536414.1536497},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HaitnerRVW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ImpagliazzoKK09,
author = {Russell Impagliazzo and
Valentine Kabanets and
Antonina Kolokolova},
editor = {Michael Mitzenmacher},
title = {An axiomatic approach to algebrization},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {695--704},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536509},
doi = {10.1145/1536414.1536509},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ImpagliazzoKK09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ImpagliazzoKW09,
author = {Russell Impagliazzo and
Valentine Kabanets and
Avi Wigderson},
editor = {Michael Mitzenmacher},
title = {New direct-product testers and 2-query PCPs},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {131--140},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536435},
doi = {10.1145/1536414.1536435},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ImpagliazzoKW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KannanN09,
author = {Ravi Kannan and
Hariharan Narayanan},
editor = {Michael Mitzenmacher},
title = {Random walks on polytopes and an affine interior point method for
linear programming},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {561--570},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536491},
doi = {10.1145/1536414.1536491},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/KannanN09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KarpinskiS09,
author = {Marek Karpinski and
Warren Schudy},
editor = {Michael Mitzenmacher},
title = {Linear time approximation schemes for the Gale-Berlekamp game and
related minimization problems},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {313--322},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536458},
doi = {10.1145/1536414.1536458},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KarpinskiS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KawarabayashiR09,
author = {Ken{-}ichi Kawarabayashi and
Bruce A. Reed},
editor = {Michael Mitzenmacher},
title = {Hadwiger's conjecture is decidable},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {445--454},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536476},
doi = {10.1145/1536414.1536476},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KawarabayashiR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KleinbergPT09,
author = {Robert Kleinberg and
Georgios Piliouras and
{\'{E}}va Tardos},
editor = {Michael Mitzenmacher},
title = {Multiplicative updates outperform generic no-regret learning in congestion
games: extended abstract},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {533--542},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536487},
doi = {10.1145/1536414.1536487},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KleinbergPT09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KolaitisK09,
author = {Phokion G. Kolaitis and
Swastik Kopparty},
editor = {Michael Mitzenmacher},
title = {Random graphs and the parity quantifier},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {705--714},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536510},
doi = {10.1145/1536414.1536510},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KolaitisK09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KunS09,
author = {G{\'{a}}bor Kun and
Mario Szegedy},
editor = {Michael Mitzenmacher},
title = {A new line of attack on the dichotomy conjecture},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {725--734},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536512},
doi = {10.1145/1536414.1536512},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KunS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KushilevitzW09,
author = {Eyal Kushilevitz and
Enav Weinreb},
editor = {Michael Mitzenmacher},
title = {On the complexity of communication complexity},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {465--474},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536479},
doi = {10.1145/1536414.1536479},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KushilevitzW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LattanziS09,
author = {Silvio Lattanzi and
D. Sivakumar},
editor = {Michael Mitzenmacher},
title = {Affiliation networks},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {427--434},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536474},
doi = {10.1145/1536414.1536474},
timestamp = {Tue, 09 Mar 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/LattanziS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LeeMNS09,
author = {Jon Lee and
Vahab S. Mirrokni and
Viswanath Nagarajan and
Maxim Sviridenko},
editor = {Michael Mitzenmacher},
title = {Non-monotone submodular maximization under matroid and knapsack constraints},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {323--332},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536459},
doi = {10.1145/1536414.1536459},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/LeeMNS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LeeS09,
author = {James R. Lee and
Anastasios Sidiropoulos},
editor = {Michael Mitzenmacher},
title = {On the geometry of graphs with a forbidden minor},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {245--254},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536450},
doi = {10.1145/1536414.1536450},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/LeeS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LinP09,
author = {Huijia Lin and
Rafael Pass},
editor = {Michael Mitzenmacher},
title = {Non-malleability amplification},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {189--198},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536442},
doi = {10.1145/1536414.1536442},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/LinP09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LinPV09,
author = {Huijia Lin and
Rafael Pass and
Muthuramakrishnan Venkitasubramaniam},
editor = {Michael Mitzenmacher},
title = {A unified framework for concurrent security: universal composability
from stand-alone non-malleability},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {179--188},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536441},
doi = {10.1145/1536414.1536441},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/LinPV09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Liu09,
author = {Yi{-}Kai Liu},
editor = {Michael Mitzenmacher},
title = {Quantum algorithms using the curvelet transform},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {391--400},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536469},
doi = {10.1145/1536414.1536469},
timestamp = {Mon, 30 Nov 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Liu09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/MartinelliS09,
author = {Fabio Martinelli and
Alistair Sinclair},
editor = {Michael Mitzenmacher},
title = {Mixing time for the solid-on-solid model},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {571--580},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536492},
doi = {10.1145/1536414.1536492},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/MartinelliS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/MathieuS09,
author = {Claire Mathieu and
Alistair Sinclair},
editor = {Michael Mitzenmacher},
title = {Sherali-adams relaxations of the matching polytope},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {293--302},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536456},
doi = {10.1145/1536414.1536456},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/MathieuS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/MontenegroT09,
author = {Ravi Montenegro and
Prasad Tetali},
editor = {Michael Mitzenmacher},
title = {How long does it take to catch a wild kangaroo?},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {553--560},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536490},
doi = {10.1145/1536414.1536490},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/MontenegroT09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Moser09,
author = {Robin A. Moser},
editor = {Michael Mitzenmacher},
title = {A constructive proof of the Lov{\'{a}}sz local lemma},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {343--350},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536462},
doi = {10.1145/1536414.1536462},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Moser09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/NguyenDT09,
author = {Nam H. Nguyen and
Thong T. Do and
Trac D. Tran},
editor = {Michael Mitzenmacher},
title = {A fast and efficient algorithm for low-rank approximation of a matrix},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {215--224},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536446},
doi = {10.1145/1536414.1536446},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/NguyenDT09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ODonnellW09,
author = {Ryan O'Donnell and
Yi Wu},
editor = {Michael Mitzenmacher},
title = {Conditional hardness for satisfiable 3-CSPs},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {493--502},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536482},
doi = {10.1145/1536414.1536482},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ODonnellW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Peikert09,
author = {Chris Peikert},
editor = {Michael Mitzenmacher},
title = {Public-key cryptosystems from the worst-case shortest vector problem:
extended abstract},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {333--342},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536461},
doi = {10.1145/1536414.1536461},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Peikert09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/RabaniS09,
author = {Yuval Rabani and
Amir Shpilka},
editor = {Michael Mitzenmacher},
title = {Explicit construction of a small epsilon-net for linear threshold
functions},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {649--658},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536502},
doi = {10.1145/1536414.1536502},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/RabaniS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Roughgarden09,
author = {Tim Roughgarden},
editor = {Michael Mitzenmacher},
title = {Intrinsic robustness of the price of anarchy},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {513--522},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536485},
doi = {10.1145/1536414.1536485},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Roughgarden09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Sellie09,
author = {Linda Sellie},
editor = {Michael Mitzenmacher},
title = {Exact learning of random {DNF} over the uniform distribution},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {45--54},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536424},
doi = {10.1145/1536414.1536424},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Sellie09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Shapira09,
author = {Asaf Shapira},
editor = {Michael Mitzenmacher},
title = {Green's conjecture and testing linear-invariant properties},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {159--166},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536438},
doi = {10.1145/1536414.1536438},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Shapira09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Sly09,
author = {Allan Sly},
editor = {Michael Mitzenmacher},
title = {Reconstruction for the Potts model},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {581--590},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536493},
doi = {10.1145/1536414.1536493},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Sly09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Ta-Shma09,
author = {Amnon Ta{-}Shma},
editor = {Michael Mitzenmacher},
title = {Short seed extractors against quantum storage},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {401--408},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536470},
doi = {10.1145/1536414.1536470},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/Ta-Shma09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Trevisan09,
author = {Luca Trevisan},
editor = {Michael Mitzenmacher},
title = {Max cut and the smallest eigenvalue},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {263--272},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536452},
doi = {10.1145/1536414.1536452},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Trevisan09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Tulsiani09,
author = {Madhur Tulsiani},
editor = {Michael Mitzenmacher},
title = {{CSP} gaps and reductions in the lasserre hierarchy},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {303--312},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536457},
doi = {10.1145/1536414.1536457},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Tulsiani09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/VassilevskaW09,
author = {Virginia Vassilevska and
Ryan Williams},
editor = {Michael Mitzenmacher},
title = {Finding, minimizing, and counting weighted subgraphs},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {455--464},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536477},
doi = {10.1145/1536414.1536477},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/VassilevskaW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Viola09,
author = {Emanuele Viola},
editor = {Michael Mitzenmacher},
title = {Bit-probe lower bounds for succinct data structures},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {475--482},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536480},
doi = {10.1145/1536414.1536480},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Viola09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Wigderson09,
author = {Avi Wigderson},
editor = {Michael Mitzenmacher},
title = {The work of Leslie Valiant},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {1--2},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536415},
doi = {10.1145/1536414.1536415},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Wigderson09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/YoshidaYI09,
author = {Yuichi Yoshida and
Masaki Yamamoto and
Hiro Ito},
editor = {Michael Mitzenmacher},
title = {An improved constant-time approximation algorithm for maximum matchings},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {225--234},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536447},
doi = {10.1145/1536414.1536447},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/YoshidaYI09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/stoc/2009,
editor = {Michael Mitzenmacher},
title = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
publisher = {{ACM}},
year = {2009},
isbn = {978-1-60558-506-2},
timestamp = {Fri, 05 Jun 2009 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/2009.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.
retrieved on 2024-04-30 17:26 CEST from data curated 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:
