default search action
43rd 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
- Mihai Patrascu, Mikkel Thorup
:
The power of simple tabulation hashing. 1-10 - 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
An optimal lower bound on the communication complexity of gap-hamming-distance. 51-60
Session 2A
- Jian Ding, James R. Lee, Yuval Peres:
Cover times, blanket times, and majorizing measures. 61-70 - 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 - Rafael Pass
Limits of provable security from standard assumptions. 109-118
Session 3A
- Christos H. Papadimitriou, George Pierrakos:
On optimal single-item auctions. 119-128 - 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
- Mark Braverman, Anup Rao:
Towards coding for maximum errors in interactive communication. 159-166 - Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin:
High-rate codes with sublinear-time decoding. 167-176 - Noga Zewi
From affine to two-source extractors via approximate duality. 177-186 - 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
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 - Ankur Moitra, Ryan O'Donnell:
Pareto optimal solutions for smoothed analysts. 225-234
Session 4B
- Kashyap Babu Rao Kolipaka, Mario Szegedy:
Moser and tardos meet Lovász. 235-244 - Robin A. Moser, Dominik Scheder
A full derandomization of schöning's k-SAT algorithm. 245-252 - Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman:
Pseudorandom generators for combinatorial shapes. 253-262 - Michal Koucký
Pseudorandom generators for group products: extended abstract. 263-272
Session 5
- Paul F. Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman
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 - Bernhard Haeupler
Analyzing network coding gossip made easy. 293-302
Session 6A
- Julia Chuzhoy:
An algorithm for the graph crossing number problem. 303-312 - Giuseppe F. Italiano
Improved algorithms for min cut and max flow in undirected planar graphs. 313-322 - Michael Dinitz
Directed spanners via flow-based linear programs. 323-332
Session 6B
- Scott Aaronson, Alex Arkhipov:
The computational complexity of linear optics. 333-342 - Fernando G. S. L. Brandão, Matthias Christandl, Jon Yard
A quasipolynomial-time algorithm for the quantum separability problem. 343-352 - Julia Kempe
Parallel repetition of entangled games. 353-362
Session 7A
- Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan
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 - Erez Kantor, Zvi Lotker, Merav Parter, David Peleg:
The topology of wireless communication. 383-392 - George Giakkoupis, Nicolas Schabanel:
Optimal path search in small worlds: dimension matters. 393-402
Session 7B
- Andrew Novocin
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
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 - Nicolas Bousquet
Multicut is FPT. 459-468 - Dániel Marx, Igor Razgon:
Fixed-parameter tractability of multicut parameterized by the size of the cutset. 469-478 - Martin Grohe
Finding topological subgraphs is fixed-parameter tractable. 479-488
Session 8B
- Swastik Kopparty:
On the complexity of powering in finite fields. 489-498 - Steve Chien, Prahladh Harsha
Almost settling the hardness of noncommutative determinant. 499-508 - Peter Bürgisser, Christian Ikenmeyer:
Geometric complexity theory and tensor rank. 509-518 - 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
- Jon M. Kleinberg, Sigal Oren
Mechanisms for (mis)allocating scientific credit. 529-538 - Richard Cole, José R. Correa, Vasilis Gkatzelis
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
- Mihai Patrascu, Mikkel Thorup
Don't rush into a union: take time to find your roots. 559-568 - Dan Feldman, Michael Langberg:
A unified framework for approximating and clustering data. 569-578 - Sunil Arya, Guilherme Dias da Fonseca
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
Almost tight bounds for reordering buffer management. 607-616 - Ola Svensson:
Santa Claus schedules jobs on unrelated machines. 617-626
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
- Manuel Bodirsky, Michael Pinsker
Schaefer's theorem for graphs. 655-664 - Yuichi Yoshida:
Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP. 665-674 - Ilan Newman, Christian Sohler
Every property of hyperfinite graphs is testable. 675-684 - 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
- Vipul Goyal:
Constant round non-malleable protocols using one way functions. 695-704 - Huijia Lin, Rafael Pass
Constant-round non-malleable commitments from any one-way function. 705-714 - Miklós Ajtai:
Secure computation with information leaking to an adversary. 715-724 - Allison B. Lewko, Mark Lewko, Brent Waters:
How to leak on key updates. 725-734 - 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 - Christian Sohler
Subspace embeddings for the L1-norm with applications. 755-764 - James R. Lee, Anastasios Sidiropoulos:
Near-optimal distortion bounds for embedding doubling spaces into L1. 765-772 - Omar Fawzi
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 - Maria-Florina Balcan, Nicholas J. A. Harvey:
Learning submodular functions. 793-802 - Anupam Gupta, Moritz Hardt, Aaron Roth
Privately releasing conjunctions and the statistical query barrier. 803-812 - Adam D. Smith:
Privacy-preserving statistical estimation with optimal convergence rates. 813-822
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.
last updated on 2024-11-22 19:46 CET 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: