43. STOC 2011: San Jose, CA, USA

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, Oded Regev:
  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(n^1/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, Eli Ben-Sasson:
  From affine to two-source extractors via approximate duality. 177-186
  
• Hamed Hatami, Shachar Lovett:
  Correlation testing for affine invariant properties on F_pⁿ 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
  
• 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ý, 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
  
• 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, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen:
  Improved algorithms for min cut and max flow in undirected planar graphs. 313-322
  
• Michael Dinitz, Robert Krauthgamer:
  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, Thomas Vidick:
  Parallel repetition of entangled games. 353-362
  

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
  
• 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, 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
  
• Nicolas Bousquet, Jean Daligault, Stéphan Thomassé:
  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, Ken-ichi Kawarabayashi, Dániel Marx, Paul Wollan:
  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, Alistair Sinclair, Srikanth Srinivasan:
  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, 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

• 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, 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
  
• 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 k² barrier for explicit RIP matrices. 637-644
  
• Zohar Shay Karnin:
  Deterministic construction of a high dimensional l_p section in l₁ⁿ 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, David P. Woodruff:
  Subspace embeddings for the L₁-norm with applications. 755-764
  
• James R. Lee, Anastasios Sidiropoulos:
  Near-optimal distortion bounds for embedding doubling spaces into L₁. 765-772
  
• Omar Fawzi, Patrick 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
  
• Maria-Florina Balcan, Nicholas J. A. Harvey:
  Learning submodular functions. 793-802
  
• Anupam Gupta, Moritz Hardt, Aaron Roth, Jonathan Ullman:
  Privately releasing conjunctions and the statistical query barrier. 803-812
  
• Adam Smith:
  Privacy-preserving statistical estimation with optimal convergence rates. 813-822
  

Last update Fri May 25 08:42:24 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page