39. STOC 2007: San Diego, California, USA

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 BibTeX

Session 1A

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

Session 1B

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

Session 2A

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

Session 2B

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

Session 3A

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

Session 3B

Elchanan Mossel, Sébastien Roch:
On the submodularity of influence in social networks. 128-134
Electronic Edition (ACM DL) BibTeX
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
Electronic Edition (ACM DL) BibTeX
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
Electronic Edition (ACM DL) BibTeX
Hagit Attiya, Keren Censor:
Tight bounds for asynchronous randomized consensus. 155-164
Electronic Edition (ACM DL) BibTeX

Session 4A

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

Session 4B

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

Session 5

Nancy A. Lynch:
Distributed computing theory: algorithms, impossibility results, models, and proofs. 247
Electronic Edition (ACM DL) BibTeX

Session 6A

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

Session 6B

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

Session 7A

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

Session 7B

Anna Pagh, Rasmus Pagh, Milan Ruzic:
Linear probing with constant independence. 318-327
Electronic Edition (ACM DL) BibTeX
Gianni Franceschini, S. Muthukrishnan:
Optimal suffix selection. 328-337
Electronic Edition (ACM DL) BibTeX

Session 8A

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

Session 8B

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

Session 9A

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

Session 9B

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

Session 10A

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

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
Electronic Edition (ACM DL) BibTeX
Peter Høyer, Troy Lee, Robert Spalek:
Negative weights make adversaries stronger. 526-535
Electronic Edition (ACM DL) BibTeX
Cristopher Moore, Alexander Russell, Piotr Sniady:
On the impossibility of a quantum sieve algorithm for graph isomorphism. 536-545
Electronic Edition (ACM DL) BibTeX

Session 11A

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

Session 11B

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

Session 12A

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

Session 12B

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

Session 13A

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

Session 13B

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