default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID39th STOC 2007: San Diego, California, USA
- David S. Johnson, Uriel Feige:
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·2osqrt(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 D. 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 AC0 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 - Patrick 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
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 2025-11-09 23:06 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:
