default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSearch dblp for Publications
export results for "toc:db/conf/stoc/stoc2010.bht:"
download as .bib file
@inproceedings{DBLP:conf/stoc/Aaronson10,
author = {Scott Aaronson},
editor = {Leonard J. Schulman},
title = {{BQP} and the polynomial hierarchy},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {141--150},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806711},
doi = {10.1145/1806689.1806711},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Aaronson10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AaronsonD10,
author = {Scott Aaronson and
Andrew Drucker},
editor = {Leonard J. Schulman},
title = {A full characterization of quantum advice},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {131--140},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806710},
doi = {10.1145/1806689.1806710},
timestamp = {Mon, 26 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AaronsonD10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Ajtai10,
author = {Mikl{\'{o}}s Ajtai},
editor = {Leonard J. Schulman},
title = {Oblivious RAMs without cryptogrpahic assumptions},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {181--190},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806716},
doi = {10.1145/1806689.1806716},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Ajtai10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AkaviaGGM10,
author = {Adi Akavia and
Oded Goldreich and
Shafi Goldwasser and
Dana Moshkovitz},
editor = {Leonard J. Schulman},
title = {Erratum for: on basing one-way functions on NP-hardness},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {795--796},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806798},
doi = {10.1145/1806689.1806798},
timestamp = {Fri, 30 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AkaviaGGM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AmbainisKS10,
author = {Andris Ambainis and
Julia Kempe and
Or Sattath},
editor = {Leonard J. Schulman},
title = {A quantum lov{\'{a}}sz local lemma},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {151--160},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806712},
doi = {10.1145/1806689.1806712},
timestamp = {Sun, 06 Oct 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/AmbainisKS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ApplebaumBW10,
author = {Benny Applebaum and
Boaz Barak and
Avi Wigderson},
editor = {Leonard J. Schulman},
title = {Public-key cryptography from different assumptions},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {171--180},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806715},
doi = {10.1145/1806689.1806715},
timestamp = {Mon, 26 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ApplebaumBW10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ArvindS10,
author = {Vikraman Arvind and
Srikanth Srinivasan},
editor = {Leonard J. Schulman},
title = {On the hardness of the noncommutative determinant},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {677--686},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806782},
doi = {10.1145/1806689.1806782},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ArvindS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BarakBCR10,
author = {Boaz Barak and
Mark Braverman and
Xi Chen and
Anup Rao},
editor = {Leonard J. Schulman},
title = {How to compress interactive communication},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {67--76},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806701},
doi = {10.1145/1806689.1806701},
timestamp = {Sat, 05 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BarakBCR10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BateniHM10,
author = {MohammadHossein Bateni and
MohammadTaghi Hajiaghayi and
D{\'{a}}niel Marx},
editor = {Leonard J. Schulman},
title = {Approximation schemes for steiner forest on planar graphs and graphs
of bounded treewidth},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {211--220},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806720},
doi = {10.1145/1806689.1806720},
timestamp = {Mon, 12 Aug 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BateniHM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BayatiGT10,
author = {Mohsen Bayati and
David Gamarnik and
Prasad Tetali},
editor = {Leonard J. Schulman},
title = {Combinatorial approach to the interpolation method and scaling limits
in sparse random graphs},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {105--114},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806706},
doi = {10.1145/1806689.1806706},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BayatiGT10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BeameHP10,
author = {Paul Beame and
Trinh Huynh and
Toniann Pitassi},
editor = {Leonard J. Schulman},
title = {Hardness amplification in proof complexity},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {87--96},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806703},
doi = {10.1145/1806689.1806703},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BeameHP10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BhaskaraCCFV10,
author = {Aditya Bhaskara and
Moses Charikar and
Eden Chlamtac and
Uriel Feige and
Aravindan Vijayaraghavan},
editor = {Leonard J. Schulman},
title = {Detecting high log-densities: an \emph{O}(\emph{n}\({}^{\mbox{1/4}}\))
approximation for densest \emph{k}-subgraph},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {201--210},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806719},
doi = {10.1145/1806689.1806719},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BhaskaraCCFV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BhattacharyaGGM10,
author = {Sayan Bhattacharya and
Gagan Goel and
Sreenivas Gollapudi and
Kamesh Munagala},
editor = {Leonard J. Schulman},
title = {Budget constrained auctions with heterogeneous items},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {379--388},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806743},
doi = {10.1145/1806689.1806743},
timestamp = {Mon, 26 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BhattacharyaGGM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BravermanO10,
author = {Vladimir Braverman and
Rafail Ostrovsky},
editor = {Leonard J. Schulman},
title = {Measuring independence of datasets},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {271--280},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806728},
doi = {10.1145/1806689.1806728},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BravermanO10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BravermanO10a,
author = {Vladimir Braverman and
Rafail Ostrovsky},
editor = {Leonard J. Schulman},
title = {Zero-one frequency laws},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {281--290},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806729},
doi = {10.1145/1806689.1806729},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BravermanO10a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BurgisserC10,
author = {Peter B{\"{u}}rgisser and
Felipe Cucker},
editor = {Leonard J. Schulman},
title = {Solving polynomial equations in smoothed polynomial time and a near
solution to smale's 17th problem},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {503--512},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806759},
doi = {10.1145/1806689.1806759},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BurgisserC10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ByrkaGRS10,
author = {Jaroslaw Byrka and
Fabrizio Grandoni and
Thomas Rothvo{\ss} and
Laura Sanit{\`{a}}},
editor = {Leonard J. Schulman},
title = {An improved LP-based approximation for steiner tree},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {583--592},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806769},
doi = {10.1145/1806689.1806769},
timestamp = {Mon, 03 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ByrkaGRS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CardinalFJJM10,
author = {Jean Cardinal and
Samuel Fiorini and
Gwena{\"{e}}l Joret and
Rapha{\"{e}}l M. Jungers and
J. Ian Munro},
editor = {Leonard J. Schulman},
title = {Sorting under partial information (without the ellipsoid algorithm)},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {359--368},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806740},
doi = {10.1145/1806689.1806740},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/CardinalFJJM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChandranKOR10,
author = {Nishanth Chandran and
Bhavana Kanukurthi and
Rafail Ostrovsky and
Leonid Reyzin},
editor = {Leonard J. Schulman},
title = {Privacy amplification with asymptotically optimal entropy loss},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {785--794},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806796},
doi = {10.1145/1806689.1806796},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChandranKOR10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChawlaHMS10,
author = {Shuchi Chawla and
Jason D. Hartline and
David L. Malec and
Balasubramanian Sivan},
editor = {Leonard J. Schulman},
title = {Multi-parameter mechanism design and sequential posted pricing},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {311--320},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806733},
doi = {10.1145/1806689.1806733},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChawlaHMS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChierichettiLP10,
author = {Flavio Chierichetti and
Silvio Lattanzi and
Alessandro Panconesi},
editor = {Leonard J. Schulman},
title = {Almost tight bounds for rumour spreading with conductance},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {399--408},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806745},
doi = {10.1145/1806689.1806745},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChierichettiLP10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DasguptaKS10,
author = {Anirban Dasgupta and
Ravi Kumar and
Tam{\'{a}}s Sarl{\'{o}}s},
editor = {Leonard J. Schulman},
title = {A sparse Johnson: Lindenstrauss transform},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {341--350},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806737},
doi = {10.1145/1806689.1806737},
timestamp = {Fri, 30 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DasguptaKS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DeV10,
author = {Anindya De and
Thomas Vidick},
editor = {Leonard J. Schulman},
title = {Near-optimal extractors against quantum storage},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {161--170},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806713},
doi = {10.1145/1806689.1806713},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/DeV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DellM10,
author = {Holger Dell and
Dieter van Melkebeek},
editor = {Leonard J. Schulman},
title = {Satisfiability allows no nontrivial sparsification unless the polynomial-time
hierarchy collapses},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {251--260},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806725},
doi = {10.1145/1806689.1806725},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/DellM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DeyHK10,
author = {Tamal K. Dey and
Anil N. Hirani and
Bala Krishnamoorthy},
editor = {Leonard J. Schulman},
title = {Optimal homologous cycles, total unimodularity, and linear programming},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {221--230},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806721},
doi = {10.1145/1806689.1806721},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DeyHK10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DiakonikolasHKMRST10,
author = {Ilias Diakonikolas and
Prahladh Harsha and
Adam R. Klivans and
Raghu Meka and
Prasad Raghavendra and
Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Leonard J. Schulman},
title = {Bounding the average sensitivity and noise sensitivity of polynomial
threshold functions},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {533--542},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806763},
doi = {10.1145/1806689.1806763},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DiakonikolasHKMRST10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DodisPT10,
author = {Yevgeniy Dodis and
Mihai P{\\u{a}}tra{\\c{s}}cu and
Mikkel Thorup},
editor = {Leonard J. Schulman},
title = {Changing base without losing space},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {593--602},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806771},
doi = {10.1145/1806689.1806771},
timestamp = {Mon, 26 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DodisPT10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DuanP10,
author = {Ran Duan and
Seth Pettie},
editor = {Leonard J. Schulman},
title = {Connectivity oracles for failure prone graphs},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {465--474},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806754},
doi = {10.1145/1806689.1806754},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DuanP10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DworkNPR10,
author = {Cynthia Dwork and
Moni Naor and
Toniann Pitassi and
Guy N. Rothblum},
editor = {Leonard J. Schulman},
title = {Differential privacy under continual observation},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {715--724},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806787},
doi = {10.1145/1806689.1806787},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DworkNPR10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DyerR10,
author = {Martin E. Dyer and
David Richerby},
editor = {Leonard J. Schulman},
title = {On the complexity of {\#}CSP},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {725--734},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806789},
doi = {10.1145/1806689.1806789},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/DyerR10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/FraigniaudG10,
author = {Pierre Fraigniaud and
George Giakkoupis},
editor = {Leonard J. Schulman},
title = {On the searchability of small-world networks with arbitrary underlying
structure},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {389--398},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806744},
doi = {10.1145/1806689.1806744},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/FraigniaudG10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/FraigniaudK10,
author = {Pierre Fraigniaud and
Amos Korman},
editor = {Leonard J. Schulman},
title = {An optimal ancestry scheme and small universal posets},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {611--620},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806773},
doi = {10.1145/1806689.1806773},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/FraigniaudK10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GaoW10,
author = {Pu Gao and
Nicholas C. Wormald},
editor = {Leonard J. Schulman},
title = {Load balancing and orientability thresholds for random hypergraphs},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {97--104},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806705},
doi = {10.1145/1806689.1806705},
timestamp = {Mon, 26 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GaoW10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GilbertLPS10,
author = {Anna C. Gilbert and
Yi Li and
Ely Porat and
Martin J. Strauss},
editor = {Leonard J. Schulman},
title = {Approximate sparse recovery: optimizing time and measurements},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {475--484},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806755},
doi = {10.1145/1806689.1806755},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GilbertLPS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GodoyGRA10,
author = {Guillem Godoy and
Omer Gim{\'{e}}nez and
Lander Ramos and
Carme {\`{A}}lvarez},
editor = {Leonard J. Schulman},
title = {The {HOM} problem is decidable},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {485--494},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806757},
doi = {10.1145/1806689.1806757},
timestamp = {Mon, 26 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GodoyGRA10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GoelKK10,
author = {Ashish Goel and
Michael Kapralov and
Sanjeev Khanna},
editor = {Leonard J. Schulman},
title = {Perfect matchings in o(\emph{n} log \emph{n}) time in regular bipartite
graphs},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {39--46},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806697},
doi = {10.1145/1806689.1806697},
timestamp = {Sun, 06 Oct 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/GoelKK10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GoyalJ10,
author = {Vipul Goyal and
Abhishek Jain},
editor = {Leonard J. Schulman},
title = {On the round complexity of covert computation},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {191--200},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806717},
doi = {10.1145/1806689.1806717},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/GoyalJ10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GuruswamiHK10,
author = {Venkatesan Guruswami and
Johan H{\aa}stad and
Swastik Kopparty},
editor = {Leonard J. Schulman},
title = {On the list-decodability of random linear codes},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {409--416},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806747},
doi = {10.1145/1806689.1806747},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/GuruswamiHK10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HaitnerRV10,
author = {Iftach Haitner and
Omer Reingold and
Salil P. Vadhan},
editor = {Leonard J. Schulman},
title = {Efficiency improvements in constructing pseudorandom generators from
one-way functions},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {437--446},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806750},
doi = {10.1145/1806689.1806750},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HaitnerRV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HaramatyS10,
author = {Elad Haramaty and
Amir Shpilka},
editor = {Leonard J. Schulman},
title = {On the structure of cubic and quartic polynomials},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {331--340},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806736},
doi = {10.1145/1806689.1806736},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/HaramatyS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HardtT10,
author = {Moritz Hardt and
Kunal Talwar},
editor = {Leonard J. Schulman},
title = {On the geometry of differential privacy},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {705--714},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806786},
doi = {10.1145/1806689.1806786},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HardtT10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HarshaKM10,
author = {Prahladh Harsha and
Adam R. Klivans and
Raghu Meka},
editor = {Leonard J. Schulman},
title = {An invariance principle for polytopes},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {543--552},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806764},
doi = {10.1145/1806689.1806764},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HarshaKM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HartlineL10,
author = {Jason D. Hartline and
Brendan Lucier},
editor = {Leonard J. Schulman},
title = {Bayesian algorithmic mechanism design},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {301--310},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806732},
doi = {10.1145/1806689.1806732},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HartlineL10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Hirai10,
author = {Hiroshi Hirai},
editor = {Leonard J. Schulman},
title = {The maximum multiflow problems with bounded fractionality},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {115--120},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806707},
doi = {10.1145/1806689.1806707},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Hirai10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HrubesWY10,
author = {Pavel Hrubes and
Avi Wigderson and
Amir Yehudayoff},
editor = {Leonard J. Schulman},
title = {Non-commutative circuits and the sum-of-squares problem},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {667--676},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806781},
doi = {10.1145/1806689.1806781},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HrubesWY10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/JainJUW10,
author = {Rahul Jain and
Zhengfeng Ji and
Sarvagya Upadhyay and
John Watrous},
editor = {Leonard J. Schulman},
title = {{QIP} = {PSPACE}},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {573--582},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806768},
doi = {10.1145/1806689.1806768},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/JainJUW10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KalaiMV10,
author = {Adam Tauman Kalai and
Ankur Moitra and
Gregory Valiant},
editor = {Leonard J. Schulman},
title = {Efficiently learning mixtures of two Gaussians},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {553--562},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806765},
doi = {10.1145/1806689.1806765},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KalaiMV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Kannan10,
author = {Ravindran Kannan},
editor = {Leonard J. Schulman},
title = {Spectral methods for matrices and tensors},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {1--12},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806691},
doi = {10.1145/1806689.1806691},
timestamp = {Mon, 26 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Kannan10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KarninMSV10,
author = {Zohar Shay Karnin and
Partha Mukhopadhyay and
Amir Shpilka and
Ilya Volkovich},
editor = {Leonard J. Schulman},
title = {Deterministic identity testing of depth-4 multilinear circuits with
bounded top fan-in},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {649--658},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806779},
doi = {10.1145/1806689.1806779},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/KarninMSV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KasiviswanathanRSU10,
author = {Shiva Prasad Kasiviswanathan and
Mark Rudelson and
Adam D. Smith and
Jonathan R. Ullman},
editor = {Leonard J. Schulman},
title = {The price of privately releasing contingency tables and the spectra
of random matrices with correlated rows},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {775--784},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806795},
doi = {10.1145/1806689.1806795},
timestamp = {Tue, 20 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/KasiviswanathanRSU10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KawamuraC10,
author = {Akitoshi Kawamura and
Stephen A. Cook},
editor = {Leonard J. Schulman},
title = {Complexity theory for operators in analysis},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {495--502},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806758},
doi = {10.1145/1806689.1806758},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KawamuraC10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KawarabayashiR10,
author = {Ken{-}ichi Kawarabayashi and
Bruce A. Reed},
editor = {Leonard J. Schulman},
title = {Odd cycle packing},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {695--704},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806785},
doi = {10.1145/1806689.1806785},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KawarabayashiR10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KawarabayashiW10,
author = {Ken{-}ichi Kawarabayashi and
Paul Wollan},
editor = {Leonard J. Schulman},
title = {A shorter proof of the graph minor algorithm: the unique linkage theorem},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {687--694},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806784},
doi = {10.1145/1806689.1806784},
timestamp = {Mon, 26 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KawarabayashiW10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Klauck10,
author = {Hartmut Klauck},
editor = {Leonard J. Schulman},
title = {A strong direct product theorem for disjointness},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {77--86},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806702},
doi = {10.1145/1806689.1806702},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Klauck10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KollaMST10,
author = {Alexandra Kolla and
Yury Makarychev and
Amin Saberi and
Shang{-}Hua Teng},
editor = {Leonard J. Schulman},
title = {Subgraph sparsification and nearly optimal ultrasparsifiers},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {57--66},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806699},
doi = {10.1145/1806689.1806699},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KollaMST10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KoppartyS10,
author = {Swastik Kopparty and
Shubhangi Saraf},
editor = {Leonard J. Schulman},
title = {Local list-decoding and testing of random linear codes from high error},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {417--426},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806748},
doi = {10.1145/1806689.1806748},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KoppartyS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KuhnLO10,
author = {Fabian Kuhn and
Nancy A. Lynch and
Rotem Oshman},
editor = {Leonard J. Schulman},
title = {Distributed computation in dynamic networks},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {513--522},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806760},
doi = {10.1145/1806689.1806760},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KuhnLO10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LeeM10,
author = {James R. Lee and
Mohammad Moharrami},
editor = {Leonard J. Schulman},
title = {Bilipschitz snowflakes and metrics of negative type},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {621--630},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806775},
doi = {10.1145/1806689.1806775},
timestamp = {Mon, 26 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/LeeM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LeeSV10,
author = {Jon Lee and
Maxim Sviridenko and
Jan Vondr{\'{a}}k},
editor = {Leonard J. Schulman},
title = {Matroid matching: the power of local search},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {369--378},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806741},
doi = {10.1145/1806689.1806741},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/LeeSV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LeightonM10,
author = {Frank Thomson Leighton and
Ankur Moitra},
editor = {Leonard J. Schulman},
title = {Extensions and limits to vertex sparsification},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {47--56},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806698},
doi = {10.1145/1806689.1806698},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/LeightonM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LokshtanovN10,
author = {Daniel Lokshtanov and
Jesper Nederlof},
editor = {Leonard J. Schulman},
title = {Saving space by algebraization},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {321--330},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806735},
doi = {10.1145/1806689.1806735},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/LokshtanovN10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Madry10,
author = {Aleksander Madry},
editor = {Leonard J. Schulman},
title = {Faster approximation schemes for fractional multicommodity flow problems
via dynamic graph algorithms},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {121--130},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806708},
doi = {10.1145/1806689.1806708},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Madry10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/MagniezMN10,
author = {Fr{\'{e}}d{\'{e}}ric Magniez and
Claire Mathieu and
Ashwin Nayak},
editor = {Leonard J. Schulman},
title = {Recognizing well-parenthesized expressions in the streaming model},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {261--270},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806727},
doi = {10.1145/1806689.1806727},
timestamp = {Mon, 18 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/MagniezMN10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Marx10,
author = {D{\'{a}}niel Marx},
editor = {Leonard J. Schulman},
title = {Tractable hypergraph properties for constraint satisfaction and conjunctive
queries},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {735--744},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806790},
doi = {10.1145/1806689.1806790},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Marx10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/MekaZ10,
author = {Raghu Meka and
David Zuckerman},
editor = {Leonard J. Schulman},
title = {Pseudorandom generators for polynomial threshold functions},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {427--436},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806749},
doi = {10.1145/1806689.1806749},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/MekaZ10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/MicciancioV10,
author = {Daniele Micciancio and
Panagiotis Voulgaris},
editor = {Leonard J. Schulman},
title = {A deterministic single exponential time algorithm for most lattice
problems based on voronoi cell computations},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {351--358},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806739},
doi = {10.1145/1806689.1806739},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/MicciancioV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Montanari10,
author = {Andrea Montanari},
editor = {Leonard J. Schulman},
title = {Message passing algorithms: a success looking for theoreticians},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {37--38},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806695},
doi = {10.1145/1806689.1806695},
timestamp = {Mon, 26 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Montanari10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/OnakR10,
author = {Krzysztof Onak and
Ronitt Rubinfeld},
editor = {Leonard J. Schulman},
title = {Maintaining a large matching and a small vertex cover},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {457--464},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806753},
doi = {10.1145/1806689.1806753},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/OnakR10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Orlin10,
author = {James B. Orlin},
editor = {Leonard J. Schulman},
title = {Improved algorithms for computing fisher's market clearing prices:
computing fisher's market clearing prices},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {291--300},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806731},
doi = {10.1145/1806689.1806731},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/Orlin10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Patrascu10,
author = {Mihai P{\\u{a}}tra{\\c{s}}cu},
editor = {Leonard J. Schulman},
title = {Towards polynomial lower bounds for dynamic problems},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {603--610},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806772},
doi = {10.1145/1806689.1806772},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Patrascu10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/PaturiP10,
author = {Ramamohan Paturi and
Pavel Pudl{\'{a}}k},
editor = {Leonard J. Schulman},
title = {On the complexity of circuit satisfiability},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {241--250},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806724},
doi = {10.1145/1806689.1806724},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/PaturiP10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/RaghavendraS10,
author = {Prasad Raghavendra and
David Steurer},
editor = {Leonard J. Schulman},
title = {Graph expansion and the unique games conjecture},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {755--764},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806792},
doi = {10.1145/1806689.1806792},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/RaghavendraS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/RaghavendraST10,
author = {Prasad Raghavendra and
David Steurer and
Prasad Tetali},
editor = {Leonard J. Schulman},
title = {Approximations for the isoperimetric and spectral profile of graphs
and related parameters},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {631--640},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806776},
doi = {10.1145/1806689.1806776},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/RaghavendraST10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Raz10,
author = {Ran Raz},
editor = {Leonard J. Schulman},
title = {Tensor-rank and lower bounds for arithmetic formulas},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {659--666},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806780},
doi = {10.1145/1806689.1806780},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/Raz10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/RothR10,
author = {Aaron Roth and
Tim Roughgarden},
editor = {Leonard J. Schulman},
title = {Interactive privacy via the median mechanism},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {765--774},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806794},
doi = {10.1145/1806689.1806794},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/RothR10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Sherstov10,
author = {Alexander A. Sherstov},
editor = {Leonard J. Schulman},
title = {Optimal bounds for sign-representing the intersection of two halfspaces
by polynomials},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {523--532},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806762},
doi = {10.1145/1806689.1806762},
timestamp = {Mon, 26 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Sherstov10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Svensson10,
author = {Ola Svensson},
editor = {Leonard J. Schulman},
title = {Conditional hardness of precedence constrained scheduling on identical
machines},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {745--754},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806791},
doi = {10.1145/1806689.1806791},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Svensson10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Talagrand10,
author = {Michel Talagrand},
editor = {Leonard J. Schulman},
title = {Are many small sets explicitly small?},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {13--36},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806693},
doi = {10.1145/1806689.1806693},
timestamp = {Mon, 26 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Talagrand10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Varadarajan10,
author = {Kasturi R. Varadarajan},
editor = {Leonard J. Schulman},
title = {Weighted geometric set cover via quasi-uniform sampling},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {641--648},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806777},
doi = {10.1145/1806689.1806777},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Varadarajan10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Vegh10,
author = {L{\'{a}}szl{\'{o}} A. V{\'{e}}gh},
editor = {Leonard J. Schulman},
title = {Augmenting undirected node-connectivity by one},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {563--572},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806767},
doi = {10.1145/1806689.1806767},
timestamp = {Fri, 09 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/Vegh10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/VerbinZ10,
author = {Elad Verbin and
Qin Zhang},
editor = {Leonard J. Schulman},
title = {The limits of buffering: a tight lower bound for dynamic membership
in the external memory model},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {447--456},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806752},
doi = {10.1145/1806689.1806752},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/VerbinZ10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Williams10,
author = {Ryan Williams},
editor = {Leonard J. Schulman},
title = {Improving exhaustive search implies superpolynomial lower bounds},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {231--240},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806723},
doi = {10.1145/1806689.1806723},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/Williams10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/stoc/2010,
editor = {Leonard J. Schulman},
title = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
publisher = {{ACM}},
year = {2010},
isbn = {978-1-4503-0050-6},
timestamp = {Fri, 12 Oct 2012 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/2010.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
retrieved on 2024-12-18 07:26 CET from data curated by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
