- Bernd Gärtner, József Solymosi, Falk Tschirschnitz, Emo Welzl, Pavel Valtr:
One line and n points. STOC 2001: 306-315 - Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin:
The round complexity of verifiable secret sharing and secure multicast. STOC 2001: 580-589 - Michel X. Goemans, David P. Williamson:
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. STOC 2001: 443-452 - Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani:
Quantum mechanical algorithms for the nonabelian hidden subgroup problem. STOC 2001: 68-74 - Martin Grohe:
Computing crossing numbers in quadratic time. STOC 2001: 231-236 - Martin Grohe, Thomas Schwentick, Luc Segoufin:
When is the evaluation of conjunctive queries tractable? STOC 2001: 657-666 - Sudipto Guha, Nick Koudas, Kyuseok Shim:
Data-streams and histograms. STOC 2001: 471-475 - Sudipto Guha, Adam Meyerson, Kamesh Munagala:
A constant factor approximation for the single sink edge installation problems. STOC 2001: 383-388 - Anupam Gupta, Jon M. Kleinberg, Amit Kumar, Rajeev Rastogi, Bülent Yener:
Provisioning a virtual private network: a network design problem for multicommodity flow. STOC 2001: 389-398 - Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim:
Private approximation of NP-hard functions. STOC 2001: 550-559 - Christian Icking, Lihong Ma:
A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D. STOC 2001: 316-321 - Kamal Jain, Vijay V. Vazirani:
Applications of approximation algorithms to cooperative games. STOC 2001: 364-372 - T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko:
Online server allocation in a server farm via benefit task systems. STOC 2001: 540-549 - Mark Jerrum, Alistair Sinclair, Eric Vigoda:
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. STOC 2001: 712-721 - Anna R. Karlin, Claire Kenyon, Dana Randall:
Dynamic TCP acknowledgement and other stories about e/(e-1). STOC 2001: 502-509 - David Kempe, Jon M. Kleinberg, Alan J. Demers:
Spatial gossip and resource location protocols. STOC 2001: 163-172 - Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, Maxim Sviridenko:
Buffer overflow management in QoS switches. STOC 2001: 520-529 - Joe Kilian, Erez Petrank:
Concurrent and resettable zero-knowledge in poly-loalgorithm rounds. STOC 2001: 560-569 - Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman:
Interaction in quantum communication and the complexity of set disjointness. STOC 2001: 124-133 - Adam R. Klivans, Daniel A. Spielman:
Randomness efficient identity testing of multivariate polynomials. STOC 2001: 216-223 - Adam R. Klivans, Rocco A. Servedio:
Learning DNF in time 2Õ(n1/3). STOC 2001: 258-265 - S. Rao Kosaraju:
Euler paths in series parallel graphs. STOC 2001: 237-240 - Oded Lachish, Ran Raz:
Explicit lower bound of 4.5n - o(n) for boolena circuits. STOC 2001: 399-408 - Marios Mavronicolas, Paul G. Spirakis:
The price of selfish routing. STOC 2001: 510-519 - Adam Meyerson:
Profit-earning facility location. STOC 2001: 30-36 - Michael Molloy, Bruce A. Reed:
Colouring graphs when the number of colours is nearly the maximum degree. STOC 2001: 462-470 - Ravi Montenegro, Jung-Bae Son:
Edge isoperimetry and rapid mixing on matroids and geometric Markov chains. STOC 2001: 704-711 - Anna Moss, Yuval Rabani:
Approximation algorithms for constrained for constrained node weighted steiner tree problems. STOC 2001: 373-382 - Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal:
Conditions on input vectors for consensus solvability in asynchronous distributed systems. STOC 2001: 153-162 - Markus Müller-Olm, Helmut Seidl:
On optimal slicing of parallel programs. STOC 2001: 647-656