39. STOC 2007: San Diego, California, USA

Session 1A

• Iftach Haitner, Omer Reingold:
  Statistically-hiding commitment from any one-way function. 1-10
  
• Jonathan Katz:
  On achieving the "best of both worlds" in secure multiparty computation. 11-20
  
• Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai:
  Zero-knowledge from secure multiparty computation. 21-30
  

Session 1B

• Timothy M. Chan, Mihai Patrascu:
  Voronoi diagrams in n·2^{osqrt(lg lg n)} time. 31-39
  
• Mihai Patrascu:
  Lower bounds for 2-dimensional range counting. 40-46
  
• Saugata Basu:
  Combinatorial complexity in O-minimal geometry. 47-56
  

Session 2A

• Martin Fürer:
  Faster integer multiplication. 57-66
  
• Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto:
  Fourier meets möbius: fast subset convolution. 67-74
  

Session 2B

• Kobbi Nissim, Sofya Raskhodnikova, Adam Smith:
  Smooth sensitivity and sampling in private data analysis. 75-84
  
• Cynthia Dwork, Frank McSherry, Kunal Talwar:
  The price of privacy and the limits of LP decoding. 85-94
  

Session 3A

• Claire Kenyon-Mathieu, Warren Schudy:
  How to rank with few errors. 95-103
  
• Sudipto Guha, Kamesh Munagala:
  Approximation algorithms for budgeted learning problems. 104-113
  
• Arash Asadpour, Amin Saberi:
  An approximation algorithm for max-min fair allocation of indivisible goods. 114-121
  
• Mohsen Bayati, David Gamarnik, Dimitriy A. Katz, Chandra Nair, Prasad Tetali:
  Simple deterministic approximation algorithms for counting matchings. 122-127
  

Session 3B

• Elchanan Mossel, Sébastien Roch:
  On the submodularity of influence in social networks. 128-134
  
• Christian Borgs, Jennifer T. Chayes, Constantinos Daskalakis, Sébastien Roch:
  First to market is not everything: an analysis of preferential attachment with fitness. 135-144
  
• Matthew Andrews, Kyomin Jung, Alexander L. Stolyar:
  Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads. 145-154
  
• Hagit Attiya, Keren Censor:
  Tight bounds for asynchronous randomized consensus. 155-164
  

Session 4A

• Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar:
  Hardness of routing with congestion in directed graphs. 165-178
  
• Julia Chuzhoy, Sanjeev Khanna:
  Polynomial flow-cut gaps and hardness of directed cut problems. 179-188
  
• Per Austrin:
  Balanced max 2-sat might not be the hardest. 189-197
  
• Venkatesan Guruswami, Prasad Raghavendra:
  A 3-query PCP over integers. 198-206
  

Session 4B

• John Dunagan, Nicholas J. A. Harvey:
  Iteratively constructing preconditioners via the conjugate gradient method. 207-216
  
• Stefan Kiefer, Michael Luttenberger, Javier Esparza:
  On the convergence of Newton's method for monotone systems of polynomial equations. 217-226
  
• Sanjeev Arora, Satyen Kale:
  A combinatorial, primal-dual approach to semidefinite programs. 227-236
  
• Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp, Roman Vershynin:
  One sketch for all: fast algorithms for compressed sensing. 237-246
  

Session 5

• Nancy A. Lynch:
  Distributed computing theory: algorithms, impossibility results, models, and proofs. 247
  

Session 6A

• Van H. Vu, Terence Tao:
  The condition number of a randomly perturbed matrix. 248-255
  
• Kunal Talwar, Udi Wieder:
  Balanced allocations: the weighted case. 256-265
  
• Sergey Yekhanin:
  Towards 3-query locally decodable codes of subexponential length. 266-274
  

Session 6B

• Rahul Santhanam:
  Circuit lower bounds for Merlin-Arthur classes. 275-283
  
• Amir Shpilka:
  Interpolation of depth-3 arithmetic circuits with two multiplication gates. 284-293
  
• Alexander A. Sherstov:
  Separating AC⁰ from depth-2 majority circuits. 294-301
  

Session 7A

• Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani:
  Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. 302-310
  
• Stefan S. Dantchev:
  Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems. 311-317
  

Session 7B

• Anna Pagh, Rasmus Pagh, Milan Ruzic:
  Linear probing with constant independence. 318-327
  
• Gianni Franceschini, S. Muthukrishnan:
  Optimal suffix selection. 328-337
  

Session 8A

• Shahar Dobzinski, Noam Nisan:
  Limitations of VCG-based mechanisms. 338-344
  
• Sergiu Hart, Yishay Mansour:
  The communication complexity of uncoupled nash equilibrium procedures. 345-353
  
• Fang Wu, Li Zhang:
  Proportional response dynamics leads to market equilibrium. 354-363
  
• Kamal Jain, Vijay V. Vazirani:
  Eisenberg-Gale markets: algorithms and structural properties. 364-373
  

Session 8B

• Pinar Heggernes, Christophe Paul, Jan Arne Telle, Yngve Villanger:
  Interval completion with few edges. 374-381
  
• Ken-ichi Kawarabayashi, Bruce A. Reed:
  Computing crossing number in linear time. 382-390
  
• Elliot Anshelevich, Adriana Karagiozova:
  Terminal backup, 3D matching, and covering cubic graphs. 391-400
  
• Jin-yi Cai, Pinyan Lu:
  Holographic algorithms: from art to science. 401-410
  

Session 9A

• Thomas Holenstein:
  Parallel repetition: simplifications and the no-signaling case. 411-419
  
• Rafael Pass, Muthuramakrishnan Venkitasubramaniam:
  An efficient parallel repetition theorem for Arthur-Merlin games. 420-429
  
• Ronen Shaltiel, Christopher Umans:
  Low-end uniform hardness vs. randomness tradeoffs for AM. 430-439
  
• Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy N. Rothblum:
  Verifying and decoding in constant depth. 440-449
  

Session 9B

• Thomas P. Hayes, Juan Carlos Vera, Eric Vigoda:
  Randomly coloring planar graphs with fewer colors than the maximum degree. 450-458
  
• Leslie Ann Goldberg, Mark Jerrum:
  Inapproximability of the Tutte polynomial. 459-468
  
• Ishay Haviv, Oded Regev:
  Tensor-based hardness of the shortest vector problem to within almost polynomial factors. 469-477
  
• Chris Peikert, Alon Rosen:
  Lattices that admit logarithmic worst-case to average-case connection factors. 478-487
  

Session 10A

• Vojtech Rödl, Mathias Schacht:
  Property testing in hypergraphs and the removal lemma. 488-495
  
• Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie:
  Testing k-wise and almost k-wise independence. 496-505
  
• Alex Samorodnitsky:
  Low-degree tests at large distances. 506-515
  

Session 10B

• Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf:
  Exponential separations for one-way quantum communication complexity, with applications to cryptography. 516-525
  
• Peter Høyer, Troy Lee, Robert Spalek:
  Negative weights make adversaries stronger. 526-535
  
• Cristopher Moore, Alexander Russell, Piotr Sniady:
  On the impossibility of a quantum sieve algorithm for graph isomorphism. 536-545
  

Session 11A

• Sham M. Kakade, Adam Tauman Kalai, Katrina Ligett:
  Playing games with approximation algorithms. 546-555
  
• Matthias Englert, Harald Räcke, Matthias Westermann:
  Reordering buffers for general metric spaces. 556-564
  

Session 11B

• Gus Gutoski, John Watrous:
  Toward a general theory of quantum games. 565-574
  
• Frédéric Magniez, Ashwin Nayak, Jeremie Roland, Miklos Santha:
  Search via quantum walk. 575-584
  

Session 12A

• Virginia Vassilevska, Ryan Williams, Raphael Yuster:
  All-pairs bottleneck paths for general graphs in truly sub-cubic time. 585-589
  
• Timothy M. Chan:
  More algorithms for all-pairs shortest paths in weighted graphs. 590-598
  
• Gyula Pap:
  Some new results on node-capacitated packing of A-paths. 599-604
  
• Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi, Anand Bhalgat:
  An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs. 605-614
  

Session 12B

• Piotr Indyk:
  Uncertainty principles, extractors, and explicit embeddings of l2 into l1. 615-620
  
• Bo Brinkman, Adriana Karagiozova, James R. Lee:
  Vertex cuts, random walks, and dimension reduction in series-parallel graphs. 621-630
  
• Ittai Abraham, Yair Bartal, Ofer Neiman:
  Local embeddings of metric spaces. 631-640
  
• Amit Deshpande, Kasturi R. Varadarajan:
  Sampling-based dimension reduction for subspace approximation. 641-650
  

Session 13A

• Lap Chi Lau, Joseph Naor, Mohammad R. Salavatipour, Mohit Singh:
  Survivable network design with degree or order constraints. 651-660
  
• Mohit Singh, Lap Chi Lau:
  Approximating minimum bounded degree spanning trees to within one of optimal. 661-670
  
• Amit Agarwal, Noga Alon, Moses Charikar:
  Improved approximation for directed cut problems. 671-680
  
• P. Donovan, F. Bruce Shepherd, Adrian Vetta, Gordon T. Wilfong:
  Degree-constrained network flows. 681-688
  

Session 13B

• Paul Beame, T. S. Jayram, Atri Rudra:
  Lower bounds for randomized read/write stream algorithms. 689-698
  
• Nati Linial, Adi Shraibman:
  Lower bounds in communication complexity based on factorization norms. 699-708
  
• Mark Braverman, Michael Yampolsky:
  Constructing non-computable Julia sets. 709-716