![](https://dblp1.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp1.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp1.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
default search action
Search dblp for Publications
export results for "toc:db/conf/stoc/stoc2008.bht:"
@inproceedings{DBLP:conf/stoc/AaronsonW08, author = {Scott Aaronson and Avi Wigderson}, editor = {Cynthia Dwork}, title = {Algebrization: a new barrier in complexity theory}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {731--740}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374481}, doi = {10.1145/1374376.1374481}, timestamp = {Wed, 14 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/AaronsonW08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/AroraKKSTV08, author = {Sanjeev Arora and Subhash Khot and Alexandra Kolla and David Steurer and Madhur Tulsiani and Nisheeth K. Vishnoi}, editor = {Cynthia Dwork}, title = {Unique games on expanding constraint graphs are easy: extended abstract}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {21--28}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374380}, doi = {10.1145/1374376.1374380}, timestamp = {Sun, 04 Aug 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/AroraKKSTV08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/AttiyaHW08, author = {Hagit Attiya and Danny Hendler and Philipp Woelfel}, editor = {Cynthia Dwork}, title = {Tight rmr lower bounds for mutual exclusion and other problems}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {217--226}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374410}, doi = {10.1145/1374376.1374410}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/AttiyaHW08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/AwerbuchK08, author = {Baruch Awerbuch and Rohit Khandekar}, editor = {Cynthia Dwork}, title = {Stateless distributed gradient descent for positive linear programs}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {691--700}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374476}, doi = {10.1145/1374376.1374476}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/AwerbuchK08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/BalcanBV08, author = {Maria{-}Florina Balcan and Avrim Blum and Santosh S. Vempala}, editor = {Cynthia Dwork}, title = {A discriminative framework for clustering via similarity functions}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {671--680}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374474}, doi = {10.1145/1374376.1374474}, timestamp = {Thu, 24 Oct 2019 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/BalcanBV08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/BansalBN08, author = {Nikhil Bansal and Niv Buchbinder and Joseph Naor}, editor = {Cynthia Dwork}, title = {Randomized competitive algorithms for generalized caching}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {235--244}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374412}, doi = {10.1145/1374376.1374412}, timestamp = {Tue, 15 Feb 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/BansalBN08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/BansalKN08, author = {Nikhil Bansal and Rohit Khandekar and Viswanath Nagarajan}, editor = {Cynthia Dwork}, title = {Additive guarantees for degree bounded directed network design}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {769--778}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374486}, doi = {10.1145/1374376.1374486}, timestamp = {Tue, 15 Feb 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/BansalKN08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/BarkolIW08, author = {Omer Barkol and Yuval Ishai and Enav Weinreb}, editor = {Cynthia Dwork}, title = {Communication in the presence of replication}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {661--670}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374472}, doi = {10.1145/1374376.1374472}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/BarkolIW08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/BartoKN08, author = {Libor Barto and Marcin Kozik and Todd Niven}, editor = {Cynthia Dwork}, title = {Graphs, polymorphisms and the complexity of homomorphism problems}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {789--796}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374488}, doi = {10.1145/1374376.1374488}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/BartoKN08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Ben-AroyaT08, author = {Avraham Ben{-}Aroya and Amnon Ta{-}Shma}, editor = {Cynthia Dwork}, title = {A combinatorial construction of almost-ramanujan graphs using the zig-zag product}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {325--334}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374424}, doi = {10.1145/1374376.1374424}, timestamp = {Sun, 02 Jun 2019 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/Ben-AroyaT08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/BenjaminiSS08, author = {Itai Benjamini and Oded Schramm and Asaf Shapira}, editor = {Cynthia Dwork}, title = {Every minor-closed property of sparse graphs is testable}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {393--402}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374433}, doi = {10.1145/1374376.1374433}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/BenjaminiSS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/BlumHLR08, author = {Avrim Blum and MohammadTaghi Hajiaghayi and Katrina Ligett and Aaron Roth}, editor = {Cynthia Dwork}, title = {Regret minimization and the price of total anarchy}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {373--382}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374430}, doi = {10.1145/1374376.1374430}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/BlumHLR08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/BlumLR08, author = {Avrim Blum and Katrina Ligett and Aaron Roth}, editor = {Cynthia Dwork}, title = {A learning theory approach to non-interactive database privacy}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {609--618}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374464}, doi = {10.1145/1374376.1374464}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/BlumLR08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/BodirskyK08, author = {Manuel Bodirsky and Jan K{\'{a}}ra}, editor = {Cynthia Dwork}, title = {The complexity of temporal constraint satisfaction problems}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {29--38}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374382}, doi = {10.1145/1374376.1374382}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/BodirskyK08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/BorgsCIKMP08, author = {Christian Borgs and Jennifer T. Chayes and Nicole Immorlica and Adam Tauman Kalai and Vahab S. Mirrokni and Christos H. Papadimitriou}, editor = {Cynthia Dwork}, title = {The myth of the folk theorem}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {365--372}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374429}, doi = {10.1145/1374376.1374429}, timestamp = {Sun, 25 Oct 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/BorgsCIKMP08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/CaiCL08, author = {Jin{-}yi Cai and Xi Chen and Dong Li}, editor = {Cynthia Dwork}, title = {A quadratic lower bound for the permanent and determinant problem over any characteristic != 2}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {491--498}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374446}, doi = {10.1145/1374376.1374446}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/CaiCL08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/ChakrabartiCM08, author = {Amit Chakrabarti and Graham Cormode and Andrew McGregor}, editor = {Cynthia Dwork}, title = {Robust lower bounds for communication and stream computation}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {641--650}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374470}, doi = {10.1145/1374376.1374470}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/ChakrabartiCM08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/ChakrabortyCK08, author = {Tanmoy Chakraborty and Julia Chuzhoy and Sanjeev Khanna}, editor = {Cynthia Dwork}, title = {Network design for vertex connectivity}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {167--176}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374403}, doi = {10.1145/1374376.1374403}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/ChakrabortyCK08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/ChenGP08, author = {Yiling Chen and Sharad Goel and David M. Pennock}, editor = {Cynthia Dwork}, title = {Pricing combinatorial markets for tournaments}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {305--314}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374421}, doi = {10.1145/1374376.1374421}, timestamp = {Thu, 08 Jul 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/ChenGP08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/ChenLL08, author = {Jianer Chen and Yang Liu and Songjian Lu and Barry O'Sullivan and Igor Razgon}, editor = {Cynthia Dwork}, title = {A fixed-parameter algorithm for the directed feedback vertex set problem}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {177--186}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374404}, doi = {10.1145/1374376.1374404}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/ChenLL08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/ChoiK08, author = {Sung{-}Soon Choi and Jeong Han Kim}, editor = {Cynthia Dwork}, title = {Optimal query complexity bounds for finding graphs}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {749--758}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374484}, doi = {10.1145/1374376.1374484}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/ChoiK08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/ColeF08, author = {Richard Cole and Lisa Fleischer}, editor = {Cynthia Dwork}, title = {Fast-converging tatonnement algorithms for one-time and ongoing market problems}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {315--324}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374422}, doi = {10.1145/1374376.1374422}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/ColeF08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/CoteMP08, author = {Aaron Cote and Adam Meyerson and Laura J. Poplawski}, editor = {Cynthia Dwork}, title = {Randomized k-server on hierarchical binary trees}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {227--234}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374411}, doi = {10.1145/1374376.1374411}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/CoteMP08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/DaitchS08, author = {Samuel I. Daitch and Daniel A. Spielman}, editor = {Cynthia Dwork}, title = {Faster approximate lossy generalized flow via interior point algorithms}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {451--460}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374441}, doi = {10.1145/1374376.1374441}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/DaitchS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/DasK08, author = {Abhimanyu Das and David Kempe}, editor = {Cynthia Dwork}, title = {Algorithms for subset selection in linear regression}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {45--54}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374384}, doi = {10.1145/1374376.1374384}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/DasK08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/DasguptaF08, author = {Sanjoy Dasgupta and Yoav Freund}, editor = {Cynthia Dwork}, title = {Random projection trees and low dimensional manifolds}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {537--546}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374452}, doi = {10.1145/1374376.1374452}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/DasguptaF08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/DeKSS08, author = {Anindya De and Piyush P. Kurur and Chandan Saha and Ramprasad Saptharishi}, editor = {Cynthia Dwork}, title = {Fast integer multiplication using modular arithmetic}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {499--506}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374447}, doi = {10.1145/1374376.1374447}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/DeKSS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/DinurGKS08, author = {Irit Dinur and Elena Grigorescu and Swastik Kopparty and Madhu Sudan}, editor = {Cynthia Dwork}, title = {Decodability of group homomorphisms beyond the johnson bound}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {275--284}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374418}, doi = {10.1145/1374376.1374418}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/DinurGKS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/DvirSY08, author = {Zeev Dvir and Amir Shpilka and Amir Yehudayoff}, editor = {Cynthia Dwork}, title = {Hardness-randomness tradeoffs for bounded depth arithmetic circuits}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {741--748}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374482}, doi = {10.1145/1374376.1374482}, timestamp = {Mon, 26 Jun 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/DvirSY08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/FakcharoenpholL08, author = {Jittat Fakcharoenphol and Bundit Laekhanukit}, editor = {Cynthia Dwork}, title = {An o(log\({}^{\mbox{2}}\) k)-approximation algorithm for the k-vertex connected spanning subgraph problem}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {153--158}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374401}, doi = {10.1145/1374376.1374401}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/FakcharoenpholL08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Feldman08, author = {Vitaly Feldman}, editor = {Cynthia Dwork}, title = {Evolvability from learning algorithms}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {619--628}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374465}, doi = {10.1145/1374376.1374465}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Feldman08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/FortnowS08, author = {Lance Fortnow and Rahul Santhanam}, editor = {Cynthia Dwork}, title = {Infeasibility of instance compression and succinct PCPs for {NP}}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {133--142}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374398}, doi = {10.1145/1374376.1374398}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/FortnowS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/FriezeVV08, author = {Alan M. Frieze and Santosh S. Vempala and Juan Vera}, editor = {Cynthia Dwork}, title = {Logconcave random graphs}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {779--788}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374487}, doi = {10.1145/1374376.1374487}, timestamp = {Wed, 06 Nov 2019 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/FriezeVV08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/GamaN08, author = {Nicolas Gama and Phong Q. Nguyen}, editor = {Cynthia Dwork}, title = {Finding short lattice vectors within mordell's inequality}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {207--216}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374408}, doi = {10.1145/1374376.1374408}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/GamaN08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Gavinsky08, author = {Dmitry Gavinsky}, editor = {Cynthia Dwork}, title = {Classical interaction cannot replace a quantum message}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {95--102}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374393}, doi = {10.1145/1374376.1374393}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Gavinsky08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/GentryPV08, author = {Craig Gentry and Chris Peikert and Vinod Vaikuntanathan}, editor = {Cynthia Dwork}, title = {Trapdoors for hard lattices and new cryptographic constructions}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {197--206}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374407}, doi = {10.1145/1374376.1374407}, timestamp = {Mon, 26 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/GentryPV08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/GoldwasserGHKR08, author = {Shafi Goldwasser and Dan Gutfreund and Alexander Healy and Tali Kaufman and Guy N. Rothblum}, editor = {Cynthia Dwork}, title = {A (de)constructive approach to program checking}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {143--152}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374399}, doi = {10.1145/1374376.1374399}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/GoldwasserGHKR08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/GoldwasserKR08, author = {Shafi Goldwasser and Yael Tauman Kalai and Guy N. Rothblum}, editor = {Cynthia Dwork}, title = {Delegating computation: interactive proofs for muggles}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {113--122}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374396}, doi = {10.1145/1374376.1374396}, timestamp = {Mon, 26 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/GoldwasserKR08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/GopalanKK08, author = {Parikshit Gopalan and Adam Tauman Kalai and Adam R. Klivans}, editor = {Cynthia Dwork}, title = {Agnostically learning decision trees}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {527--536}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374451}, doi = {10.1145/1374376.1374451}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/GopalanKK08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/GopalanKZ08, author = {Parikshit Gopalan and Adam R. Klivans and David Zuckerman}, editor = {Cynthia Dwork}, title = {List-decoding reed-muller codes over small fields}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {265--274}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374417}, doi = {10.1145/1374376.1374417}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/GopalanKZ08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/GordonHKL08, author = {S. Dov Gordon and Carmit Hazay and Jonathan Katz and Yehuda Lindell}, editor = {Cynthia Dwork}, title = {Complete fairness in secure two-party computation}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {413--422}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374436}, doi = {10.1145/1374376.1374436}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/GordonHKL08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/GoyalOS08, author = {Navin Goyal and Neil Olver and F. Bruce Shepherd}, editor = {Cynthia Dwork}, title = {The vpn conjecture is true}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {443--450}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374440}, doi = {10.1145/1374376.1374440}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/GoyalOS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/HartlineR08, author = {Jason D. Hartline and Tim Roughgarden}, editor = {Cynthia Dwork}, title = {Optimal mechanism design and money burning}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {75--84}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374390}, doi = {10.1145/1374376.1374390}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/HartlineR08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Haussler08, author = {David Haussler}, editor = {Cynthia Dwork}, title = {Computing how we became human}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {639--640}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374468}, doi = {10.1145/1374376.1374468}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Haussler08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/ImpagliazzoJKW08, author = {Russell Impagliazzo and Ragesh Jaiswal and Valentine Kabanets and Avi Wigderson}, editor = {Cynthia Dwork}, title = {Uniform direct product theorems: simplified, optimized, and derandomized}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {579--588}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374460}, doi = {10.1145/1374376.1374460}, timestamp = {Tue, 07 May 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/ImpagliazzoJKW08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/IshaiKOS08, author = {Yuval Ishai and Eyal Kushilevitz and Rafail Ostrovsky and Amit Sahai}, editor = {Cynthia Dwork}, title = {Cryptography with constant computational overhead}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {433--442}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374438}, doi = {10.1145/1374376.1374438}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/IshaiKOS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/JainKN08, author = {Rahul Jain and Hartmut Klauck and Ashwin Nayak}, editor = {Cynthia Dwork}, title = {Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {599--608}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374462}, doi = {10.1145/1374376.1374462}, timestamp = {Mon, 18 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/JainKN08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/JubaS08, author = {Brendan Juba and Madhu Sudan}, editor = {Cynthia Dwork}, title = {Universal semantic communication {I}}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {123--132}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374397}, doi = {10.1145/1374376.1374397}, timestamp = {Tue, 14 Jun 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/JubaS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/KalaiMV08, author = {Adam Tauman Kalai and Yishay Mansour and Elad Verbin}, editor = {Cynthia Dwork}, title = {On agnostic boosting and parity learning}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {629--638}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374466}, doi = {10.1145/1374376.1374466}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/KalaiMV08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/KaufmanS08, author = {Tali Kaufman and Madhu Sudan}, editor = {Cynthia Dwork}, title = {Algebraic property testing: the role of invariance}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {403--412}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374434}, doi = {10.1145/1374376.1374434}, timestamp = {Tue, 14 Jun 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/KaufmanS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/KawarabayashiM08, author = {Ken{-}ichi Kawarabayashi and Bojan Mohar}, editor = {Cynthia Dwork}, title = {Graph and map isomorphism and all polyhedral embeddings in linear time}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {471--480}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374443}, doi = {10.1145/1374376.1374443}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/KawarabayashiM08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/KhotS08, author = {Subhash Khot and Rishi Saket}, editor = {Cynthia Dwork}, title = {On hardness of learning intersection of two halfspaces}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {345--354}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374426}, doi = {10.1145/1374376.1374426}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/KhotS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/KleinbergSU08, author = {Robert Kleinberg and Aleksandrs Slivkins and Eli Upfal}, editor = {Cynthia Dwork}, title = {Multi-armed bandits in metric spaces}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {681--690}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374475}, doi = {10.1145/1374376.1374475}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/KleinbergSU08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/KleinbergT08, author = {Jon M. Kleinberg and {\'{E}}va Tardos}, editor = {Cynthia Dwork}, title = {Balanced outcomes in social exchange networks}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {295--304}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1376994}, doi = {10.1145/1374376.1376994}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/KleinbergT08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/KolN08, author = {Gillat Kol and Moni Naor}, editor = {Cynthia Dwork}, title = {Games for exchanging information}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {423--432}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374437}, doi = {10.1145/1374376.1374437}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/KolN08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/LauS08, author = {Lap Chi Lau and Mohit Singh}, editor = {Cynthia Dwork}, title = {Additive approximation for bounded degree survivable network design}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {759--768}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374485}, doi = {10.1145/1374376.1374485}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/LauS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/LevinSZ08, author = {Hagay Levin and Michael Schapira and Aviv Zohar}, editor = {Cynthia Dwork}, title = {Interdomain routing and games}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {57--66}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374388}, doi = {10.1145/1374376.1374388}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/LevinSZ08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Lovett08, author = {Shachar Lovett}, editor = {Cynthia Dwork}, title = {Unconditional pseudorandom generators for low degree polynomials}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {557--562}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374455}, doi = {10.1145/1374376.1374455}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Lovett08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/LovettMS08, author = {Shachar Lovett and Roy Meshulam and Alex Samorodnitsky}, editor = {Cynthia Dwork}, title = {Inverse conjecture for the gowers norm is false}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {547--556}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374454}, doi = {10.1145/1374376.1374454}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/LovettMS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/ManokaranNRS08, author = {Rajsekar Manokaran and Joseph Naor and Prasad Raghavendra and Roy Schwartz}, editor = {Cynthia Dwork}, title = {Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {11--20}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374379}, doi = {10.1145/1374376.1374379}, timestamp = {Wed, 23 Dec 2020 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/ManokaranNRS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Meir08, author = {Or Meir}, editor = {Cynthia Dwork}, title = {Combinatorial construction of locally testable codes}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {285--294}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374419}, doi = {10.1145/1374376.1374419}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Meir08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/MironovNS08, author = {Ilya Mironov and Moni Naor and Gil Segev}, editor = {Cynthia Dwork}, title = {Sketching in adversarial environments}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {651--660}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374471}, doi = {10.1145/1374376.1374471}, timestamp = {Sun, 16 Jun 2019 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/MironovNS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Nandakumar08, author = {Satyadev Nandakumar}, editor = {Cynthia Dwork}, title = {An effective ergodic theorem and some applications}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {39--44}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374383}, doi = {10.1145/1374376.1374383}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Nandakumar08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/NordstromH08, author = {Jakob Nordstr{\"{o}}m and Johan H{\aa}stad}, editor = {Cynthia Dwork}, title = {Towards an optimal separation of space and length in resolution}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {701--710}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374478}, doi = {10.1145/1374376.1374478}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/NordstromH08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/ODonnell08, author = {Ryan O'Donnell}, editor = {Cynthia Dwork}, title = {Some topics in analysis of boolean functions}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {569--578}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374458}, doi = {10.1145/1374376.1374458}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/ODonnell08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/ODonnellS08, author = {Ryan O'Donnell and Rocco A. Servedio}, editor = {Cynthia Dwork}, title = {The chow parameters problem}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {517--526}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374450}, doi = {10.1145/1374376.1374450}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/ODonnellS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/ODonnellW08, author = {Ryan O'Donnell and Yi Wu}, editor = {Cynthia Dwork}, title = {An optimal sdp algorithm for max-cut, and equally optimal long code tests}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {335--344}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374425}, doi = {10.1145/1374376.1374425}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/ODonnellW08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/OrecchiaSVV08, author = {Lorenzo Orecchia and Leonard J. Schulman and Umesh V. Vazirani and Nisheeth K. Vishnoi}, editor = {Cynthia Dwork}, title = {On partitioning graphs via single commodity flows}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {461--470}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374442}, doi = {10.1145/1374376.1374442}, timestamp = {Tue, 21 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/OrecchiaSVV08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/PeikertW08, author = {Chris Peikert and Brent Waters}, editor = {Cynthia Dwork}, title = {Lossy trapdoor functions and their applications}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {187--196}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374406}, doi = {10.1145/1374376.1374406}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/PeikertW08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Racke08, author = {Harald R{\"{a}}cke}, editor = {Cynthia Dwork}, title = {Optimal hierarchical decompositions for congestion minimization in networks}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {255--264}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374415}, doi = {10.1145/1374376.1374415}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Racke08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Raghavendra08, author = {Prasad Raghavendra}, editor = {Cynthia Dwork}, title = {Optimal algorithms and inapproximability results for every CSP?}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {245--254}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374414}, doi = {10.1145/1374376.1374414}, timestamp = {Wed, 14 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Raghavendra08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Rao08, author = {Anup Rao}, editor = {Cynthia Dwork}, title = {Parallel repetition in projection games and a concentration bound}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {1--10}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374378}, doi = {10.1145/1374376.1374378}, timestamp = {Thu, 03 Sep 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/Rao08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Raz08, author = {Ran Raz}, editor = {Cynthia Dwork}, title = {Elusive functions and lower bounds for arithmetic circuits}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {711--720}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374479}, doi = {10.1145/1374376.1374479}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/Raz08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/ReichardtS08, author = {Ben Reichardt and Robert Spalek}, editor = {Cynthia Dwork}, title = {Span-program-based quantum algorithm for evaluating formulas}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {103--112}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374394}, doi = {10.1145/1374376.1374394}, timestamp = {Wed, 14 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/ReichardtS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Rexford08, author = {Jennifer Rexford}, editor = {Cynthia Dwork}, title = {Rethinking internet routing}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {55--56}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374386}, doi = {10.1145/1374376.1374386}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Rexford08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Rossman08, author = {Benjamin Rossman}, editor = {Cynthia Dwork}, title = {On the constant-depth complexity of k-clique}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {721--730}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374480}, doi = {10.1145/1374376.1374480}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Rossman08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/ShaltielV08, author = {Ronen Shaltiel and Emanuele Viola}, editor = {Cynthia Dwork}, title = {Hardness amplification proofs require majority}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {589--598}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374461}, doi = {10.1145/1374376.1374461}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/ShaltielV08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Sherstov08, author = {Alexander A. Sherstov}, editor = {Cynthia Dwork}, title = {The pattern matrix method for lower bounds on quantum communication}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {85--94}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374392}, doi = {10.1145/1374376.1374392}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Sherstov08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/ShpilkaV08, author = {Amir Shpilka and Ilya Volkovich}, editor = {Cynthia Dwork}, title = {Read-once polynomial identity testing}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {507--516}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374448}, doi = {10.1145/1374376.1374448}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/ShpilkaV08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/SkopalikV08, author = {Alexander Skopalik and Berthold V{\"{o}}cking}, editor = {Cynthia Dwork}, title = {Inapproximability of pure nash equilibria}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {355--364}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374428}, doi = {10.1145/1374376.1374428}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/SkopalikV08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/SpielmanS08, author = {Daniel A. Spielman and Nikhil Srivastava}, editor = {Cynthia Dwork}, title = {Graph sparsification by effective resistances}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {563--568}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374456}, doi = {10.1145/1374376.1374456}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/SpielmanS08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Thorup08, author = {Mikkel Thorup}, editor = {Cynthia Dwork}, title = {Minimum k-way cuts via deterministic greedy tree packing}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {159--166}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374402}, doi = {10.1145/1374376.1374402}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Thorup08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Umans08, author = {Christopher Umans}, editor = {Cynthia Dwork}, title = {Fast polynomial factorization and modular composition in small characteristic}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {481--490}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374445}, doi = {10.1145/1374376.1374445}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Umans08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Valiant08, author = {Paul Valiant}, editor = {Cynthia Dwork}, title = {Testing symmetric properties of distributions}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {383--392}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374432}, doi = {10.1145/1374376.1374432}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Valiant08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Vondrak08, author = {Jan Vondr{\'{a}}k}, editor = {Cynthia Dwork}, title = {Optimal approximation for the submodular welfare problem in the value oracle model}, booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, pages = {67--74}, publisher = {{ACM}}, year = {2008}, url = {https://doi.org/10.1145/1374376.1374389}, doi = {10.1145/1374376.1374389}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Vondrak08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@proceedings{DBLP:conf/stoc/2008, editor = {Cynthia Dwork}, title = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, publisher = {{ACM}}, year = {2008}, isbn = {978-1-60558-047-0}, timestamp = {Sat, 19 Jun 2010 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/stoc/2008.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
![](https://dblp1.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.