Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic Scholar43rd STOC 2011: San Jose, CA, USA
Lance Fortnow, Salil P. Vadhan:
Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011. ACM 2011, ISBN 978-1-4503-0691-1
Session 1A
- Christoph Lenzen, Roger Wattenhofer:
Tight bounds for parallel randomized load balancing: extended abstract. 11-20 - Benjamin Doerr, Mahmoud Fouz, Tobias Friedrich:
Social networks spread rumors in sublogarithmic time. 21-30
Session 1B
- Oded Regev, Bo'az Klartag:
Quantum one-way communication can be exponentially stronger than classical communication. 31-40 - Alexander A. Sherstov:
Strong direct product theorems for quantum communication and query complexity. 41-50 - Amit Chakrabarti, Oded Regev:
An optimal lower bound on the communication complexity of gap-hamming-distance. 51-60
Session 2A
- Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, Debmalya Panigrahi:
A general framework for graph sparsification. 71-80 - Ken-ichi Kawarabayashi, Yusuke Kobayashi:
Breaking o(n1/2)-approximation algorithms for the edge-disjoint paths problem with congestion two. 81-88
Session 2B
- Thomas Holenstein, Robin Künzler, Stefano Tessaro:
The equivalence of the random oracle model and the ideal cipher model, revisited. 89-98 - Craig Gentry, Daniel Wichs:
Separating succinct non-interactive arguments from all falsifiable assumptions. 99-108
Session 3A
- Shahar Dobzinski, Hu Fu, Robert D. Kleinberg:
Optimal auctions with correlated bidders are easy. 129-138 - Shahar Dobzinski:
An impossibility result for truthful combinatorial auctions with submodular valuations. 139-148 - Shaddin Dughmi, Tim Roughgarden, Qiqi Yan:
From convex optimization to randomized mechanisms: toward optimal combinatorial auctions. 149-158
Session 3B
- Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin:
High-rate codes with sublinear-time decoding. 167-176 - Hamed Hatami, Shachar Lovett:
Correlation testing for affine invariant properties on Fpn in the high error regime. 187-194
Session 4A
- Bharat Adsul, Jugal Garg, Ruta Mehta, Milind A. Sohoni:
Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm. 195-204 - Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas:
Exact algorithms for solving stochastic games: extended abstract. 205-214 - Nicole Immorlica, Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, Moshe Tennenholtz:
Dueling algorithms. 215-224
Session 4B
- Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman:
Pseudorandom generators for combinatorial shapes. 253-262 - Michal Koucký, Prajakta Nimbhorkar, Pavel Pudlák:
Pseudorandom generators for group products: extended abstract. 263-272
Session 5
- Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, Shang-Hua Teng:
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. 273-282 - Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick:
Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. 283-292
Session 6A
- Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen:
Improved algorithms for min cut and max flow in undirected planar graphs. 313-322
Session 6B
- Fernando G. S. L. Brandão, Matthias Christandl, Jon Yard:
A quasipolynomial-time algorithm for the quantum separability problem. 343-352
Session 7A
- Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer:
Distributed verification and hardness of distributed approximation. 363-372 - Wojciech M. Golab, Lisa Higham, Philipp Woelfel:
Linearizable implementations do not suffice for randomized distributed computation. 373-382 - George Giakkoupis, Nicolas Schabanel:
Optimal path search in small worlds: dimension matters. 393-402
Session 7B
- Andrew Novocin, Damien Stehlé, Gilles Villard:
An LLL-reduction algorithm with quasi-linear time complexity: extended abstract. 403-412 - Subhash Khot, Dana Moshkovitz:
NP-hardness of approximately solving linear equations over reals. 413-420 - Shubhangi Saraf, Ilya Volkovich:
Black-box identity testing of depth-4 multilinear circuits. 421-430 - Nitin Saxena, C. Seshadhri:
Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter. 431-440
Session 8A
- Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi:
Contraction decomposition in h-minor-free graphs and algorithmic applications. 441-450 - Ken-ichi Kawarabayashi, Paul Wollan:
A simpler algorithm and shorter proof for the graph minor decomposition. 451-458 - Dániel Marx, Igor Razgon:
Fixed-parameter tractability of multicut parameterized by the size of the cutset. 469-478 - Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, Paul Wollan:
Finding topological subgraphs is fixed-parameter tractable. 479-488
Session 8B
- Steve Chien, Prahladh Harsha, Alistair Sinclair, Srikanth Srinivasan:
Almost settling the hardness of noncommutative determinant. 499-508 - Boaz Barak, Zeev Dvir, Amir Yehudayoff, Avi Wigderson:
Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes. 519-528
Session 9A
- Richard Cole, José R. Correa, Vasilis Gkatzelis, Vahab S. Mirrokni, Neil Olver:
Inner product spaces for MinSum coordination mechanisms. 539-548 - Uriel Feige, Moshe Tennenholtz:
Mechanism design with uncertain inputs: (to err is human, to forgive divine). 549-558
Session 9B
- Sunil Arya, Guilherme Dias da Fonseca, David M. Mount:
Approximate polytope membership queries. 579-586
Session 10A
- Chinmay Karande, Aranyak Mehta, Pushkar Tripathi:
Online bipartite matching with unknown distributions. 587-596 - Mohammad Mahdian, Qiqi Yan:
Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. 597-606 - Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke:
Almost tight bounds for reordering buffer management. 607-616
Session 10B
- Piotr Indyk, Eric Price:
K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance. 627-636 - Jean Bourgain, Stephen J. Dilworth, Kevin Ford, Sergei Konyagin, Denka Kutzarova:
Breaking the k2 barrier for explicit RIP matrices. 637-644 - Zohar Shay Karnin:
Deterministic construction of a high dimensional lp section in l1n for any p<2. 645-654
Session 11A
- Yuichi Yoshida:
Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP. 665-674 - Gregory Valiant, Paul Valiant:
Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs. 685-694
Session 11B
- Huijia Lin, Rafael Pass:
Constant-round non-malleable commitments from any one-way function. 705-714 - David P. Woodruff:
Near-optimal private approximation protocols via a black box transformation. 735-744
Session 12A
- Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff:
Fast moment estimation in data streams in optimal space. 745-754 - James R. Lee, Anastasios Sidiropoulos:
Near-optimal distortion bounds for embedding doubling spaces into L1. 765-772 - Omar Fawzi, Patrick M. Hayden, Pranab Sen:
From low-distortion norm embeddings to explicit uncertainty relations and efficient information locking. 773-782
Session 12B
- Jan Vondrák, Chandra Chekuri, Rico Zenklusen:
Submodular function maximization via the multilinear relaxation and contention resolution schemes. 783-792 - Anupam Gupta, Moritz Hardt, Aaron Roth, Jonathan Ullman:
Privately releasing conjunctions and the statistical query barrier. 803-812
maintained by 
, founded at 
, founded at 
last updated on 2019-01-16 22:12 CET by the dblp team
data released under the ODC-BY 1.0 license
see also: Terms of Use | Privacy Policy | Imprint