![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Search dblp for Publications
export results for "toc:db/conf/stoc/stoc2009.bht:"
@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 = {Sun, 04 Aug 2024 01:00:00 +0200}, 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, 07 May 2024 01:00:00 +0200}, 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, 07 May 2024 01:00:00 +0200}, 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 = {Sun, 04 Aug 2024 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} }
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
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.