default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSearch dblp for Publications
export results for "toc:db/conf/stoc/stoc2007.bht:"
download as .bib file
@inproceedings{DBLP:conf/stoc/AbrahamBN07,
author = {Ittai Abraham and
Yair Bartal and
Ofer Neiman},
editor = {David S. Johnson and
Uriel Feige},
title = {Local embeddings of metric spaces},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {631--640},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250883},
doi = {10.1145/1250790.1250883},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AbrahamBN07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AgarwalAC07,
author = {Amit Agarwal and
Noga Alon and
Moses Charikar},
editor = {David S. Johnson and
Uriel Feige},
title = {Improved approximation for directed cut problems},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {671--680},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250888},
doi = {10.1145/1250790.1250888},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/AgarwalAC07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AlonAKMRX07,
author = {Noga Alon and
Alexandr Andoni and
Tali Kaufman and
Kevin Matulef and
Ronitt Rubinfeld and
Ning Xie},
editor = {David S. Johnson and
Uriel Feige},
title = {Testing k-wise and almost k-wise independence},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {496--505},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250863},
doi = {10.1145/1250790.1250863},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AlonAKMRX07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AndrewsJS07,
author = {Matthew Andrews and
Kyomin Jung and
Alexander L. Stolyar},
editor = {David S. Johnson and
Uriel Feige},
title = {Stability of the max-weight routing and scheduling protocol in dynamic
networks and at critical loads},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {145--154},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250813},
doi = {10.1145/1250790.1250813},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AndrewsJS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AnshelevichK07,
author = {Elliot Anshelevich and
Adriana Karagiozova},
editor = {David S. Johnson and
Uriel Feige},
title = {Terminal backup, 3D matching, and covering cubic graphs},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {391--400},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250849},
doi = {10.1145/1250790.1250849},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/AnshelevichK07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AroraK07,
author = {Sanjeev Arora and
Satyen Kale},
editor = {David S. Johnson and
Uriel Feige},
title = {A combinatorial, primal-dual approach to semidefinite programs},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {227--236},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250823},
doi = {10.1145/1250790.1250823},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AroraK07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AsadpourS07,
author = {Arash Asadpour and
Amin Saberi},
editor = {David S. Johnson and
Uriel Feige},
title = {An approximation algorithm for max-min fair allocation of indivisible
goods},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {114--121},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250808},
doi = {10.1145/1250790.1250808},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AsadpourS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AttiyaC07,
author = {Hagit Attiya and
Keren Censor},
editor = {David S. Johnson and
Uriel Feige},
title = {Tight bounds for asynchronous randomized consensus},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {155--164},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250814},
doi = {10.1145/1250790.1250814},
timestamp = {Mon, 16 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/AttiyaC07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Austrin07,
author = {Per Austrin},
editor = {David S. Johnson and
Uriel Feige},
title = {Balanced max 2-sat might not be the hardest},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {189--197},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250818},
doi = {10.1145/1250790.1250818},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Austrin07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Basu07,
author = {Saugata Basu},
editor = {David S. Johnson and
Uriel Feige},
title = {Combinatorial complexity in O-minimal geometry},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {47--56},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250798},
doi = {10.1145/1250790.1250798},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Basu07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BayatiGKNT07,
author = {Mohsen Bayati and
David Gamarnik and
Dimitriy A. Katz and
Chandra Nair and
Prasad Tetali},
editor = {David S. Johnson and
Uriel Feige},
title = {Simple deterministic approximation algorithms for counting matchings},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {122--127},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250809},
doi = {10.1145/1250790.1250809},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BayatiGKNT07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BeameJR07,
author = {Paul Beame and
T. S. Jayram and
Atri Rudra},
editor = {David S. Johnson and
Uriel Feige},
title = {Lower bounds for randomized read/write stream algorithms},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {689--698},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250891},
doi = {10.1145/1250790.1250891},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BeameJR07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BjorklundHKK07,
author = {Andreas Bj{\"{o}}rklund and
Thore Husfeldt and
Petteri Kaski and
Mikko Koivisto},
editor = {David S. Johnson and
Uriel Feige},
title = {Fourier meets m{\"{o}}bius: fast subset convolution},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {67--74},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250801},
doi = {10.1145/1250790.1250801},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BjorklundHKK07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BorgsCDR07,
author = {Christian Borgs and
Jennifer T. Chayes and
Constantinos Daskalakis and
S{\'{e}}bastien Roch},
editor = {David S. Johnson and
Uriel Feige},
title = {First to market is not everything: an analysis of preferential attachment
with fitness},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {135--144},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250812},
doi = {10.1145/1250790.1250812},
timestamp = {Sun, 06 Oct 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BorgsCDR07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BravermanY07,
author = {Mark Braverman and
Michael Yampolsky},
editor = {David S. Johnson and
Uriel Feige},
title = {Constructing non-computable Julia sets},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {709--716},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250893},
doi = {10.1145/1250790.1250893},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BravermanY07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BrinkmanKL07,
author = {Bo Brinkman and
Adriana Karagiozova and
James R. Lee},
editor = {David S. Johnson and
Uriel Feige},
title = {Vertex cuts, random walks, and dimension reduction in series-parallel
graphs},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {621--630},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250882},
doi = {10.1145/1250790.1250882},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BrinkmanKL07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CaiL07,
author = {Jin{-}yi Cai and
Pinyan Lu},
editor = {David S. Johnson and
Uriel Feige},
title = {Holographic algorithms: from art to science},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {401--410},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250850},
doi = {10.1145/1250790.1250850},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/CaiL07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Chan07,
author = {Timothy M. Chan},
editor = {David S. Johnson and
Uriel Feige},
title = {More algorithms for all-pairs shortest paths in weighted graphs},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {590--598},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250877},
doi = {10.1145/1250790.1250877},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Chan07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChanP07,
author = {Timothy M. Chan and
Mihai P{\\u{a}}tra{\\c{s}}cu},
editor = {David S. Johnson and
Uriel Feige},
title = {Voronoi diagrams in n{\(\cdot\)}2\({}^{\mbox{osqrt(lg lg n)}}\) time},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {31--39},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250796},
doi = {10.1145/1250790.1250796},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChanP07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChuzhoyGKT07,
author = {Julia Chuzhoy and
Venkatesan Guruswami and
Sanjeev Khanna and
Kunal Talwar},
editor = {David S. Johnson and
Uriel Feige},
title = {Hardness of routing with congestion in directed graphs},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {165--178},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250816},
doi = {10.1145/1250790.1250816},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChuzhoyGKT07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChuzhoyK07,
author = {Julia Chuzhoy and
Sanjeev Khanna},
editor = {David S. Johnson and
Uriel Feige},
title = {Polynomial flow-cut gaps and hardness of directed cut problems},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {179--188},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250817},
doi = {10.1145/1250790.1250817},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChuzhoyK07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Dantchev07,
author = {Stefan S. Dantchev},
editor = {David S. Johnson and
Uriel Feige},
title = {Rank complexity gap for Lov{\'{a}}sz-Schrijver and Sherali-Adams
proof systems},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {311--317},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250837},
doi = {10.1145/1250790.1250837},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Dantchev07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DeshpandeV07,
author = {Amit Deshpande and
Kasturi R. Varadarajan},
editor = {David S. Johnson and
Uriel Feige},
title = {Sampling-based dimension reduction for subspace approximation},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {641--650},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250884},
doi = {10.1145/1250790.1250884},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DeshpandeV07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DobzinskiN07,
author = {Shahar Dobzinski and
Noam Nisan},
editor = {David S. Johnson and
Uriel Feige},
title = {Limitations of VCG-based mechanisms},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {338--344},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250842},
doi = {10.1145/1250790.1250842},
timestamp = {Sun, 25 Oct 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/DobzinskiN07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DonovanSVW07,
author = {Patrick Donovan and
F. Bruce Shepherd and
Adrian Vetta and
Gordon T. Wilfong},
editor = {David S. Johnson and
Uriel Feige},
title = {Degree-constrained network flows},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {681--688},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250889},
doi = {10.1145/1250790.1250889},
timestamp = {Tue, 09 Mar 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DonovanSVW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DunaganH07,
author = {John Dunagan and
Nicholas J. A. Harvey},
editor = {David S. Johnson and
Uriel Feige},
title = {Iteratively constructing preconditioners via the conjugate gradient
method},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {207--216},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250821},
doi = {10.1145/1250790.1250821},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DunaganH07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DworkMT07,
author = {Cynthia Dwork and
Frank McSherry and
Kunal Talwar},
editor = {David S. Johnson and
Uriel Feige},
title = {The price of privacy and the limits of {LP} decoding},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {85--94},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250804},
doi = {10.1145/1250790.1250804},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DworkMT07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/EnglertRW07,
author = {Matthias Englert and
Harald R{\"{a}}cke and
Matthias Westermann},
editor = {David S. Johnson and
Uriel Feige},
title = {Reordering buffers for general metric spaces},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {556--564},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250871},
doi = {10.1145/1250790.1250871},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/EnglertRW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/FranceschiniM07,
author = {Gianni Franceschini and
S. Muthukrishnan},
editor = {David S. Johnson and
Uriel Feige},
title = {Optimal suffix selection},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {328--337},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250840},
doi = {10.1145/1250790.1250840},
timestamp = {Mon, 10 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/FranceschiniM07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Furer07,
author = {Martin F{\"{u}}rer},
editor = {David S. Johnson and
Uriel Feige},
title = {Faster integer multiplication},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {57--66},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250800},
doi = {10.1145/1250790.1250800},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Furer07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GavinskyKKRW07,
author = {Dmitry Gavinsky and
Julia Kempe and
Iordanis Kerenidis and
Ran Raz and
Ronald de Wolf},
editor = {David S. Johnson and
Uriel Feige},
title = {Exponential separations for one-way quantum communication complexity,
with applications to cryptography},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {516--525},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250866},
doi = {10.1145/1250790.1250866},
timestamp = {Sun, 06 Oct 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/GavinskyKKRW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GilbertSTV07,
author = {Anna C. Gilbert and
Martin J. Strauss and
Joel A. Tropp and
Roman Vershynin},
editor = {David S. Johnson and
Uriel Feige},
title = {One sketch for all: fast algorithms for compressed sensing},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {237--246},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250824},
doi = {10.1145/1250790.1250824},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GilbertSTV07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GoldbergJ07,
author = {Leslie Ann Goldberg and
Mark Jerrum},
editor = {David S. Johnson and
Uriel Feige},
title = {Inapproximability of the Tutte polynomial},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {459--468},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250858},
doi = {10.1145/1250790.1250858},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GoldbergJ07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GoldwasserGHKR07,
author = {Shafi Goldwasser and
Dan Gutfreund and
Alexander Healy and
Tali Kaufman and
Guy N. Rothblum},
editor = {David S. Johnson and
Uriel Feige},
title = {Verifying and decoding in constant depth},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {440--449},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250855},
doi = {10.1145/1250790.1250855},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GoldwasserGHKR07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GuhaM07,
author = {Sudipto Guha and
Kamesh Munagala},
editor = {David S. Johnson and
Uriel Feige},
title = {Approximation algorithms for budgeted learning problems},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {104--113},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250807},
doi = {10.1145/1250790.1250807},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/GuhaM07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GuruswamiR07,
author = {Venkatesan Guruswami and
Prasad Raghavendra},
editor = {David S. Johnson and
Uriel Feige},
title = {A 3-query {PCP} over integers},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {198--206},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250819},
doi = {10.1145/1250790.1250819},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GuruswamiR07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GutoskiW07,
author = {Gus Gutoski and
John Watrous},
editor = {David S. Johnson and
Uriel Feige},
title = {Toward a general theory of quantum games},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {565--574},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250873},
doi = {10.1145/1250790.1250873},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GutoskiW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HaitnerR07,
author = {Iftach Haitner and
Omer Reingold},
editor = {David S. Johnson and
Uriel Feige},
title = {Statistically-hiding commitment from any one-way function},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {1--10},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250792},
doi = {10.1145/1250790.1250792},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HaitnerR07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HariharanKPB07,
author = {Ramesh Hariharan and
Telikepalli Kavitha and
Debmalya Panigrahi and
Anand Bhalgat},
editor = {David S. Johnson and
Uriel Feige},
title = {An {\~{O}}(mn) Gomory-Hu tree construction algorithm for unweighted
graphs},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {605--614},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250879},
doi = {10.1145/1250790.1250879},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HariharanKPB07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HartM07,
author = {Sergiu Hart and
Yishay Mansour},
editor = {David S. Johnson and
Uriel Feige},
title = {The communication complexity of uncoupled nash equilibrium procedures},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {345--353},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250843},
doi = {10.1145/1250790.1250843},
timestamp = {Fri, 09 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/HartM07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HavivR07,
author = {Ishay Haviv and
Oded Regev},
editor = {David S. Johnson and
Uriel Feige},
title = {Tensor-based hardness of the shortest vector problem to within almost
polynomial factors},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {469--477},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250859},
doi = {10.1145/1250790.1250859},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HavivR07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HayesVV07,
author = {Thomas P. Hayes and
Juan Carlos Vera and
Eric Vigoda},
editor = {David S. Johnson and
Uriel Feige},
title = {Randomly coloring planar graphs with fewer colors than the maximum
degree},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {450--458},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250857},
doi = {10.1145/1250790.1250857},
timestamp = {Fri, 27 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HayesVV07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HeggernesPTV07,
author = {Pinar Heggernes and
Christophe Paul and
Jan Arne Telle and
Yngve Villanger},
editor = {David S. Johnson and
Uriel Feige},
title = {Interval completion with few edges},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {374--381},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250847},
doi = {10.1145/1250790.1250847},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HeggernesPTV07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Holenstein07,
author = {Thomas Holenstein},
editor = {David S. Johnson and
Uriel Feige},
title = {Parallel repetition: simplifications and the no-signaling case},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {411--419},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250852},
doi = {10.1145/1250790.1250852},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Holenstein07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HoyerLS07,
author = {Peter H{\o}yer and
Troy Lee and
Robert Spalek},
editor = {David S. Johnson and
Uriel Feige},
title = {Negative weights make adversaries stronger},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {526--535},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250867},
doi = {10.1145/1250790.1250867},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/HoyerLS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Indyk07,
author = {Piotr Indyk},
editor = {David S. Johnson and
Uriel Feige},
title = {Uncertainty principles, extractors, and explicit embeddings of l2
into l1},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {615--620},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250881},
doi = {10.1145/1250790.1250881},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Indyk07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/IshaiKOS07,
author = {Yuval Ishai and
Eyal Kushilevitz and
Rafail Ostrovsky and
Amit Sahai},
editor = {David S. Johnson and
Uriel Feige},
title = {Zero-knowledge from secure multiparty computation},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {21--30},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250794},
doi = {10.1145/1250790.1250794},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/IshaiKOS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/JainV07,
author = {Kamal Jain and
Vijay V. Vazirani},
editor = {David S. Johnson and
Uriel Feige},
title = {Eisenberg-Gale markets: algorithms and structural properties},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {364--373},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250845},
doi = {10.1145/1250790.1250845},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/JainV07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KakadeKL07,
author = {Sham M. Kakade and
Adam Tauman Kalai and
Katrina Ligett},
editor = {David S. Johnson and
Uriel Feige},
title = {Playing games with approximation algorithms},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {546--555},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250870},
doi = {10.1145/1250790.1250870},
timestamp = {Fri, 09 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/KakadeKL07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Katz07,
author = {Jonathan Katz},
editor = {David S. Johnson and
Uriel Feige},
title = {On achieving the "best of both worlds" in secure multiparty computation},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {11--20},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250793},
doi = {10.1145/1250790.1250793},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Katz07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KawarabayashiR07,
author = {Ken{-}ichi Kawarabayashi and
Bruce A. Reed},
editor = {David S. Johnson and
Uriel Feige},
title = {Computing crossing number in linear time},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {382--390},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250848},
doi = {10.1145/1250790.1250848},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KawarabayashiR07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Kenyon-MathieuS07,
author = {Claire Kenyon{-}Mathieu and
Warren Schudy},
editor = {David S. Johnson and
Uriel Feige},
title = {How to rank with few errors},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {95--103},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250806},
doi = {10.1145/1250790.1250806},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Kenyon-MathieuS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KieferLE07,
author = {Stefan Kiefer and
Michael Luttenberger and
Javier Esparza},
editor = {David S. Johnson and
Uriel Feige},
title = {On the convergence of Newton's method for monotone systems of polynomial
equations},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {217--226},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250822},
doi = {10.1145/1250790.1250822},
timestamp = {Fri, 09 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/KieferLE07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LauNSS07,
author = {Lap Chi Lau and
Joseph Naor and
Mohammad R. Salavatipour and
Mohit Singh},
editor = {David S. Johnson and
Uriel Feige},
title = {Survivable network design with degree or order constraints},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {651--660},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250886},
doi = {10.1145/1250790.1250886},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/LauNSS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LinialS07,
author = {Nati Linial and
Adi Shraibman},
editor = {David S. Johnson and
Uriel Feige},
title = {Lower bounds in communication complexity based on factorization norms},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {699--708},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250892},
doi = {10.1145/1250790.1250892},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/LinialS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Lynch07,
author = {Nancy A. Lynch},
editor = {David S. Johnson and
Uriel Feige},
title = {Distributed computing theory: algorithms, impossibility results, models,
and proofs},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {247},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250826},
doi = {10.1145/1250790.1250826},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Lynch07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/MagniezNRS07,
author = {Fr{\'{e}}d{\'{e}}ric Magniez and
Ashwin Nayak and
J{\'{e}}r{\'{e}}mie Roland and
Miklos Santha},
editor = {David S. Johnson and
Uriel Feige},
title = {Search via quantum walk},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {575--584},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250874},
doi = {10.1145/1250790.1250874},
timestamp = {Mon, 18 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/MagniezNRS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/MooreRS07,
author = {Cristopher Moore and
Alexander Russell and
Piotr Sniady},
editor = {David S. Johnson and
Uriel Feige},
title = {On the impossibility of a quantum sieve algorithm for graph isomorphism},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {536--545},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250868},
doi = {10.1145/1250790.1250868},
timestamp = {Mon, 03 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/MooreRS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/MosselR07,
author = {Elchanan Mossel and
S{\'{e}}bastien Roch},
editor = {David S. Johnson and
Uriel Feige},
title = {On the submodularity of influence in social networks},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {128--134},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250811},
doi = {10.1145/1250790.1250811},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/MosselR07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/NissimRS07,
author = {Kobbi Nissim and
Sofya Raskhodnikova and
Adam D. Smith},
editor = {David S. Johnson and
Uriel Feige},
title = {Smooth sensitivity and sampling in private data analysis},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {75--84},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250803},
doi = {10.1145/1250790.1250803},
timestamp = {Tue, 20 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/NissimRS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/PaghPR07,
author = {Anna Pagh and
Rasmus Pagh and
Milan Ruzic},
editor = {David S. Johnson and
Uriel Feige},
title = {Linear probing with constant independence},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {318--327},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250839},
doi = {10.1145/1250790.1250839},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/PaghPR07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Pap07,
author = {Gyula Pap},
editor = {David S. Johnson and
Uriel Feige},
title = {Some new results on node-capacitated packing of A-paths},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {599--604},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250878},
doi = {10.1145/1250790.1250878},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Pap07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/PassV07,
author = {Rafael Pass and
Muthuramakrishnan Venkitasubramaniam},
editor = {David S. Johnson and
Uriel Feige},
title = {An efficient parallel repetition theorem for Arthur-Merlin games},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {420--429},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250853},
doi = {10.1145/1250790.1250853},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/PassV07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Patrascu07,
author = {Mihai P{\\u{a}}tra{\\c{s}}cu},
editor = {David S. Johnson and
Uriel Feige},
title = {Lower bounds for 2-dimensional range counting},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {40--46},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250797},
doi = {10.1145/1250790.1250797},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Patrascu07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/PeikertR07,
author = {Chris Peikert and
Alon Rosen},
editor = {David S. Johnson and
Uriel Feige},
title = {Lattices that admit logarithmic worst-case to average-case connection
factors},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {478--487},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250860},
doi = {10.1145/1250790.1250860},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/PeikertR07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/RodlS07,
author = {Vojtech R{\"{o}}dl and
Mathias Schacht},
editor = {David S. Johnson and
Uriel Feige},
title = {Property testing in hypergraphs and the removal lemma},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {488--495},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250862},
doi = {10.1145/1250790.1250862},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/RodlS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Samorodnitsky07,
author = {Alex Samorodnitsky},
editor = {David S. Johnson and
Uriel Feige},
title = {Low-degree tests at large distances},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {506--515},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250864},
doi = {10.1145/1250790.1250864},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Samorodnitsky07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Santhanam07,
author = {Rahul Santhanam},
editor = {David S. Johnson and
Uriel Feige},
title = {Circuit lower bounds for Merlin-Arthur classes},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {275--283},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250832},
doi = {10.1145/1250790.1250832},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Santhanam07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/SchoenebeckTT07,
author = {Grant Schoenebeck and
Luca Trevisan and
Madhur Tulsiani},
editor = {David S. Johnson and
Uriel Feige},
title = {Tight integrality gaps for Lovasz-Schrijver {LP} relaxations of vertex
cover and max cut},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {302--310},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250836},
doi = {10.1145/1250790.1250836},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/SchoenebeckTT07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ShaltielU07,
author = {Ronen Shaltiel and
Christopher Umans},
editor = {David S. Johnson and
Uriel Feige},
title = {Low-end uniform hardness vs. randomness tradeoffs for {AM}},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {430--439},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250854},
doi = {10.1145/1250790.1250854},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ShaltielU07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Sherstov07,
author = {Alexander A. Sherstov},
editor = {David S. Johnson and
Uriel Feige},
title = {Separating AC\({}^{\mbox{0}}\) from depth-2 majority circuits},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {294--301},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250834},
doi = {10.1145/1250790.1250834},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Sherstov07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Shpilka07,
author = {Amir Shpilka},
editor = {David S. Johnson and
Uriel Feige},
title = {Interpolation of depth-3 arithmetic circuits with two multiplication
gates},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {284--293},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250833},
doi = {10.1145/1250790.1250833},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/Shpilka07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/SinghL07,
author = {Mohit Singh and
Lap Chi Lau},
editor = {David S. Johnson and
Uriel Feige},
title = {Approximating minimum bounded degree spanning trees to within one
of optimal},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {661--670},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250887},
doi = {10.1145/1250790.1250887},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/SinghL07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/TalwarW07,
author = {Kunal Talwar and
Udi Wieder},
editor = {David S. Johnson and
Uriel Feige},
title = {Balanced allocations: the weighted case},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {256--265},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250829},
doi = {10.1145/1250790.1250829},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/TalwarW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/VassilevskaWY07,
author = {Virginia Vassilevska and
Ryan Williams and
Raphael Yuster},
editor = {David S. Johnson and
Uriel Feige},
title = {All-pairs bottleneck paths for general graphs in truly sub-cubic time},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {585--589},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250876},
doi = {10.1145/1250790.1250876},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/VassilevskaWY07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/VuT07,
author = {Van H. Vu and
Terence Tao},
editor = {David S. Johnson and
Uriel Feige},
title = {The condition number of a randomly perturbed matrix},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {248--255},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250828},
doi = {10.1145/1250790.1250828},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/VuT07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/WuZ07,
author = {Fang Wu and
Li Zhang},
editor = {David S. Johnson and
Uriel Feige},
title = {Proportional response dynamics leads to market equilibrium},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {354--363},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250844},
doi = {10.1145/1250790.1250844},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/WuZ07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Yekhanin07,
author = {Sergey Yekhanin},
editor = {David S. Johnson and
Uriel Feige},
title = {Towards 3-query locally decodable codes of subexponential length},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {266--274},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250830},
doi = {10.1145/1250790.1250830},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Yekhanin07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/stoc/2007,
editor = {David S. Johnson and
Uriel Feige},
title = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
publisher = {{ACM}},
year = {2007},
isbn = {978-1-59593-631-8},
timestamp = {Wed, 13 Jun 2007 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/2007.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-11-13 20:43 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:
