• 
  David S. Johnson, Uriel Feige (Eds.): Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007. ACM 2007 ISBN 978-1-59593-631-8

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, Jérémie 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