ACM Symposium on Theory of Computing
2005
- Spectral norm of random matricesby: Van H. Vu
- The complexity of agreementby: Scott Aaronson
- Testing versus estimation of graph propertiesby: Eldar Fischer, Ilan Newman
- Hardness of the undirected edge-disjoint paths problemby: Matthew Andrews, Lisa Zhang
- Fast quantum algorithms for computing the unit group and class group of a number fieldby: Sean Hallgren
- Key agreement from weak bit agreementby: Thomas Holenstein
- Hierarchies for semantic classesby: Lance Fortnow, Rahul Santhanam, Luca Trevisan
- Approximately counting integral flows and cell-bounded contingency tablesby: Mary Cryan, Martin E. Dyer, Dana Randall
- Convex programming for scheduling unrelated parallel machinesby: Yossi Azar, Amir Epstein
- Edge partition of planar sraphs into two outerplanar graphsby: Daniel Gonçalves
- Towards strong nonapproximability results in the Lovasz-Schrijver hierarchyby: Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis
- Lower bounds for k-DNF resolution on random 3-CNFsby: Michael Alekhnovich
- Computing correlated equilibria in multi-player gamesby: Christos H. Papadimitriou
- Improved approximation algorithms for minimum-weight vertex separatorsby: Uriel Feige, Mohammad Taghi Hajiaghayi, James R. Lee
- An O(log n log log n) space algorithm for undirected st-connectivityby: Vladimir Trifonov
- Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuitsby: Zeev Dvir, Amir Shpilka
- Derandomization of auctionsby: Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan
- From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreementby: Eli Gafni, Rachid Guerraoui, Bastian Pochon
- Learning nonsingular phylogenies and hidden Markov modelsby: Elchanan Mossel, Sébastien Roch
- On strip packing With rotationsby: Klaus Jansen, Rob van Stee
- An optimal multi-writer snapshot algorithmby: Prasad Jayanti
- The mixing time of the Thorp shuffleby: Ben Morris
- Covert two-party computationby: Luis von Ahn, Nicholas J. Hopper, John Langford
- Hardness of the undirected congestion minimization problemby: Matthew Andrews, Lisa Zhang
- Quadratic forms on graphsby: Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
- Cooperative asynchronous update of shared memoryby: Bogdan S. Chlebus, Dariusz R. Kowalski
- Lower-stretch spanning treesby: Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng
- On non-uniform multicommodity buy-at-bulk network designby: Moses Charikar, Adriana Karagiozova
- Beyond NP: the work and legacy of Larry Stockmeyerby: Lance Fortnow
- New and improved constructions of non-malleable cryptographic protocolsby: Rafael Pass, Alon Rosen
- Bounded-depth circuits: separating wires from gatesby: Michal Koucký, Pavel Pudlák, Denis Thérien
- Market equilibrium via the excess demand functionby: Bruno Codenotti, Benton McCune, Kasturi R. Varadarajan
- Tree-walking automata do not recognize all regular languagesby: Mikolaj Bojanczyk, Thomas Colcombet
- Correcting errors without leaking partial informationby: Yevgeniy Dodis, Adam Smith
- Large the price of routing unsplittable flowby: Baruch Awerbuch, Yossi Azar, Amir Epstein
- Approximation techniques for utilitarian mechanism designby: Patrick Briest, Piotr Krysta, Berthold Vöcking
- Testing monotone high-dimensional distributionsby: Ronitt Rubinfeld, Rocco A. Servedio
- Optimal approximations of the frequency moments of data streamsby: Piotr Indyk, David P. Woodruff
- Multicommodity flow, well-linked terminals, and routing problemsby: Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
- Tensor decomposition and approximation schemes for constraint satisfaction problemsby: Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh Vempala
- Limits to list decoding Reed-Solomon codesby: Venkatesan Guruswami, Atri Rudra
- Pseudorandom generators for low degree polynomialsby: Andrej Bogdanov
- Extractors with weak random seedsby: Ran Raz
- Saving an epsilon: a 2-approximation for the k-MST problem in graphsby: Naveen Garg
- Learning with attribute costsby: Haim Kaplan, Eyal Kushilevitz, Yishay Mansour
- Tensor norms and the classical communication complexity of nonlocal quantum measurementby: Yaoyun Shi
- Aggregating inconsistent information: ranking and clusteringby: Nir Ailon, Moses Charikar, Alantha Newman
- The price of anarchy of finite congestion gamesby: George Christodoulou, Elias Koutsoupias
- Approximation algorithms for combinatorial auctions with complement-free biddersby: Shahar Dobzinski, Noam Nisan, Michael Schapira
- Euclidean distortion and the sparsest cutby: Sanjeev Arora, James R. Lee, Assaf Naor
- On uniform amplification of hardness in NPby: Luca Trevisan
- On the bias of traceroute sampling: or, power-law degree distributions in regular graphsby: Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore
- On algorithms for discrete and approximate brouwer fixed pointsby: Xi Chen, Xiaotie Deng
- Every monotone graph property is testableby: Noga Alon, Asaf Shapira
- On random pm 1 matrices: singularity and determinantby: Terence Tao, Van H. Vu
- Balanced metric labelingby: Joseph Naor, Roy Schwartz
- Simple PCPs with poly-log rate and query complexityby: Eli Ben-Sasson, Madhu Sudan
- Undirected ST-connectivity in log-spaceby: Omer Reingold
- On obfuscating point functionsby: Hoeteck Wee
- Collusion-free protocolsby: Matt Lepinski, Silvio Micali, Abhi Shelat
- O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problemsby: Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev
- How to spread adversarial nodes?: rotate!by: Christian Scheideler
- On lattices, learning with errors, random linear codes, and cryptographyby: Oded Regev
- Low-distortion embeddings of general metrics into the lineby: Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos
- Towards asymptotic optimality in probabilistic packet markingby: Micah Adler, Jeff Edmonds, Jirí Matousek
- Efficient testing of groupsby: Katalin Friedl, Gábor Ivanyos, Miklos Santha
- Oblivious routing in directed graphs with random demandsby: Mohammad Taghi Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Räcke
- Representing hard lattices with O(n log n) bitsby: Miklós Ajtai
- Worst-case update times for fully-dynamic all-pairs shortest pathsby: Mikkel Thorup
- Universal approximations for TSP, Steiner tree, and set coverby: Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, Ravi Sundaram
- Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractorsby: Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson
- Coresets in dynamic geometric data streamsby: Gereon Frahling, Christian Sohler
- Computing the first Betti number and the connected components of semi-algebraic setsby: Saugata Basu, Richard Pollack, Marie-Françoise Roy
- Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalitiesby: Saugata Basu
- Low distortion embeddings for edit distanceby: Rafail Ostrovsky, Yuval Rabani
- The round complexity of two-party random selectionby: Saurabh Sanghvi, Salil P. Vadhan
- A new strategy for querying priced informationby: Ferdinando Cicalese, Eduardo Sany Laber
- Every 2-CSP allows nontrivial approximationby: Johan Håstad
- Approximation algorithms for network design with metric costsby: Joseph Cheriyan, Adrian Vetta
- Concurrent general composition of secure protocols in the timing modelby: Yael Tauman Kalai, Yehuda Lindell, Manoj Prabhakaran
- On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problemby: Abraham Flaxman, Alan M. Frieze, Juan C. Vera
- On dynamic range reporting in one dimensionby: Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu
- Polynomial time quantum algorithm for the computation of the unit group of a number fieldby: Arthur Schmidt, Ulrich Vollmer
- Balanced boolean functions that can be evaluated so that every input bit is unlikely to be readby: Itai Benjamini, Oded Schramm, David B. Wilson
- Fast quantum byzantine agreementby: Michael Ben-Or, Avinatan Hassidim
- Multi-linear formulas for permanent and determinant are of super-polynomial sizeby: Ran Raz
- Completeness in two-party secure computation: a computational viewby: Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen
- A new PCP outer verifier with applications to homogeneous linear equations and max-bisectionby: Jonas Holmerin, Subhash Khot
- Sharp thresholds For monotone properties in random geometric graphsby: Ashish Goel, Sanatan Rai, Bhaskar Krishnamachari
- A decentralized algorithm for spectral analysisby: David Kempe, Frank McSherry
- The difficulty of testing for isomorphism against a graph that is given in advanceby: Eldar Fischer
- Linear FPT reductions and computational lower boundsby: Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia
- Quantum and classical query complexities of local search are polynomially relatedby: Miklos Santha, Mario Szegedy
- Know thy neighbor's neighbor: the power of lookahead in randomized P2P networksby: Gurmeet Singh Manku, Moni Naor, Udi Wieder
- Multilinear formulas and skepticism of quantum computingby: Scott Aaronson
- Using nondeterminism to amplify hardnessby: Alexander Healy, Salil P. Vadhan, Emanuele Viola
- Quantum algorithms a decade after shorby: Andris Ambainis
- A new family of Cayley expanders (?)by: Eyal Rozenman, Aner Shalev, Avi Wigderson
- Sorting and searching in the presence of memory faults (without redundancy)by: Irene Finocchi, Giuseppe F. Italiano
- Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genusby: Jonathan A. Kelner
- Batch codes and their applicationsby: Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
- Auction algorithms for market equilibriumby: Rahul Garg, Sanjiv Kapoor
- Exponential separation of quantum and classical one-way communication complexityby: Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis
- On sums of independent random variables with unbounded variance, and estimating the average degree in a graphby: Uriel Feige
- Dictionary matching and indexing with errors and don't caresby: Richard Cole, Lee-Ad Gottlieb, Moshe Lewenstein
- An approximate König's theorem for edge-coloring weighted bipartite graphsby: José R. Correa, Michel X. Goemans
- The all-or-nothing multicommodity flow problemby: Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
- Adaptive routing with end-to-end feedback: distributed learning and geometric approachesby: Baruch Awerbuch, Robert D. Kleinberg
- On coresets for k-means and k-median clusteringby: Sariel Har-Peled, Soham Mazumdar
- The quantum adiabatic optimization algorithm and local minimaby: Ben Reichardt
- Algorithms for dynamic geometric problems over data streamsby: Piotr Indyk
- Approximation algorithms for deadline-TSP and vehicle routing with time-windowsby: Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson
- Sublinear algorithms for testing monotone and unimodal distributionsby: Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld
- A simple polynomial-time rescaling algorithm for solving linear programsby: John Dunagan, Santosh Vempala
- Computing Nash equilibria for scheduling on restricted parallel linksby: Martin Gairing, Thomas Lücking, Marios Mavronicolas, Burkhard Monien
- New hardness results for congestion minimization and machine schedulingby: Julia Chuzhoy, Joseph Naor
- Estimating the weight of metric minimum spanning trees in sublinear-timeby: Artur Czumaj, Christian Sohler
- Bounded-concurrent secure multi-party computation with a dishonest majorityby: Rafael Pass
- Typical properties of winners and losers in discrete optimizationby: René Beier, Berthold Vöcking
- Solving fractional packing problems in Oast(1/?) iterationsby: Daniel Bienstock, Garud Iyengar
- Asymmetric k-center is log* n-hard to approximateby: Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor
- Low distortion maps between point setsby: Claire Kenyon, Yuval Rabani, Alistair Sinclair
- Bypassing the embedding: algorithms for low dimensional metricsby: Kunal Talwar
- Finding paths and cycles of superpolylogarithmic lengthby: Harold N. Gabow
- The zero-one principle for switching networksby: Yossi Azar, Yossi Richter
- Using mixture models for collaborative filteringby: Jon M. Kleinberg, Mark Sandler
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systemsby: Daniel A. Spielman, Shang-Hua Teng
- Multi-processor scheduling to minimize flow time with epsilon resource augmentationby: Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar
- Collective asynchronous reading with polylogarithmic worst-case overheadby: Bogdan S. Chlebus, Dariusz R. Kowalski, Alexander A. Shvartsman
- Derandomizing homomorphism testing in general groupsby: Amir Shpilka, Avi Wigderson
- Boosted sampling: approximation algorithms for stochastic optimizationby: Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha
- The complexity of pure Nash equilibriaby: Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar
- A fully dynamic reachability algorithm for directed graphs with an almost linear update timeby: Liam Roditty, Uri Zwick
- The spending constraint model for market equilibrium: algorithmic, existence and uniqueness resultsby: Nikhil R. Devanur
- (Almost) tight bounds and existence theorems for confluent flowsby: Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta
- Approximate max-integral-flow/min-multicut theoremsby: Kenji Obata
- Graph entropy and quantum sorting problemsby: Andrew Chi-Chih Yao
- New notions of security: achieving universal composability without trusted setupby: Manoj Prabhakaran, Amit Sahai
- Primal-dual algorithms for deterministic inventory problemsby: Retsef Levi, Robin Roundy, David B. Shmoys
- Lower bounds for linear degeneracy testingby: Nir Ailon, Bernard Chazelle
- Approximation algorithm for k-node connected subgraphs via critical graphsby: Guy Kortsarz, Zeev Nutov
- On the performance of greedy algorithms in packet bufferingby: Susanne Albers, Markus Schmidt
- Counting complexity classes for numeric computations II: algebraic and semialgebraic setsby: Peter Bürgisser, Felipe Cucker
- Rational secret sharing and multiparty computation: extended abstractby: Joseph Y. Halpern, Vanessa Teague
- Hit-and-run from a cornerby: László Lovász, Santosh Vempala
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problemby: Michael Elkin
- Visibly pushdown languagesby: Rajeev Alur, P. Madhusudan
- The two possible values of the chromatic number of a random graphby: Dimitris Achlioptas, Assaf Naor
- Robust pcps of proximity, shorter pcps and applications to codingby: Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan
- Lower bounds for dynamic connectivityby: Mihai Patrascu, Erik D. Demaine
- Depth through breadth, or why should we attend talks in other areas?by: Avi Wigderson
- Network gamesby: Éva Tardos
- A conjecture about polynomial time computable lattice-lattice functionsby: Miklós Ajtai
- Better extractors for better codes?by: Venkatesan Guruswami
- Approximating the cut-norm via Grothendieck's inequalityby: Noga Alon, Assaf Naor
- Isotopic implicit surface meshingby: Jean-Daniel Boissonnat, David Cohen-Steiner, Gert Vegter
- Expander flows, geometric embeddings and graph partitioningby: Sanjeev Arora, Satish Rao, Umesh V. Vazirani
- Lower bounds for local search by quantum argumentsby: Scott Aaronson
- The computational complexity of some julia setsby: Robert Rettinger, Klaus Weihrauch
- On the power of quantum fingerprintingby: Andrew Chi-Chih Ya
- The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a latticeby: Miklós Ajtai
- Polylogarithmic inapproximabilityby: Eran Halperin, Robert Krauthgamer
- Meet and merge: approximation algorithms for confluent flowsby: Jiangzhuo Chen, Rajmohan Rajaraman, Ravi Sundaram
- Testing subgraphs in directed graphsby: Noga Alon, Asaf Shapira
- Work-competitive scheduling for cooperative computing with dynamic groupsby: Chryssis Georgiou, Alexander Russell, Alexander A. Shvartsman
- Sublinear geometric algorithmsby: Bernard Chazelle, Ding Liu, Avner Magen
- Random knapsack in expected polynomial timeby: René Beier, Berthold Vöcking
- Non-interactive and reusable non-malleable commitment schemesby: Ivan Damgård, Jens Groth
- Approximate counting by dynamic programmingby: Martin E. Dyer
- Distinct distances in three and higher dimensionsby: Boris Aronov, János Pach, Micha Sharir, Gábor Tardos
- Lower bounds on the amount of randomness in private computationby: Anna Gál, Adi Rosén
- Well-separated pair decomposition for the unit-disk graph metric and its applicationsby: Jie Gao, Li Zhang
- On the fractal behavior of TCPby: Anna C. Gilbert, Howard J. Karloff
- Server scheduling in the Lp norm: a rising tide lifts all boatby: Nikhil Bansal, Kirk Pruhs
- Short path queries in planar graphs in constant timeby: Lukasz Kowalik, Maciej Kurowski
- Uniform hashing in constant time and linear spaceby: Anna Östlin, Rasmus Pagh
- Generating random regular graphsby: Jeong Han Kim, Van H. Vu
- Sampling lower bounds via information theoryby: Ziv Bar-Yossef
- Pricing network edges for heterogeneous selfish usersby: Richard Cole, Yevgeniy Dodis, Tim Roughgarden
- Primal-dual meets local search: approximating MST's with nonuniform degree boundsby: Jochen Könemann, R. Ravi
- Reconstructing curves in three (and higher) dimensional space from noisy databy: Don Coppersmith, Madhu Sudan
- A sublinear algorithm for weakly approximating edit distanceby: Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami
- A tight bound on approximating arbitrary metrics by tree metricsby: Jittat Fakcharoenphol, Satish Rao, Kunal Talwar
- Some 3CNF properties are hard to testby: Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova
- Exponential algorithmic speedup by a quantum walkby: Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman
- Management of multi-queue switches in QoS networksby: Yossi Azar, Yossi Richter
- Near-optimal network design with selfish agentsby: Elliot Anshelevich, Anirban Dasgupta, Éva Tardos, Tom Wexler
- Randomness-efficient low degree tests and short PCPs via epsilon-biased setsby: Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson
- Simpler and better approximation algorithms for network designby: Anupam Gupta, Amit Kumar, Tim Roughgarden
- Evolving sets and mixinby: Ben Morris, Yuval Peres
- On the limits of cache-obliviousnessby: Gerth Stølting Brodal, Rolf Fagerberg
- A tight time lower bound for space-optimal implementations of multi-writer snapshotsby: Panagiota Fatourou, Faith E. Fich, Eric Ruppert
- A stochastic process on the hypercube with applications to peer-to-peer networksby: Micah Adler, Eran Halperin, Richard M. Karp, Vijay V. Vazirani
- Bounded-concurrent secure two-party computation without setup assumptionsby: Yehuda Lindell
- OPT versus LOAD in dynamic storage allocationby: Adam L. Buchsbaum, Howard J. Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup
- Quantum time-space tradeoffs for sortingby: Hartmut Klauck
- Linear time encodable and list decodable codesby: Venkatesan Guruswami, Piotr Indyk
- The intrinsic dimensionality of graphsby: Robert Krauthgamer, James R. Lee
- New degree bounds for polynomial threshold functionsby: Ryan O'Donnell, Rocco A. Servedio
- A fast algorithm for computing steiner edge connectivityby: Richard Cole, Ramesh Hariharan
- Alpha-shapes and flow shapes are homotopy equivalentby: Tamal K. Dey, Joachim Giesen, Matthias John
- Dynamic rectangular intersection with prioritiesby: Haim Kaplan, Eyal Molad, Robert Endre Tarjan
- A new multilayered PCP and the hardness of hypergraph vertex coverby: Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
- Two applications of information complexityby: T. S. Jayram, Ravi Kumar, D. Sivakumar
- New lattice based cryptographic constructionsby: Oded Regev
- Integer priority queues with decrease key in constant time and the single source shortest paths problemby: Mikkel Thorup
- Cutting triangular cycles of lines in spaceby: Boris Aronov, Vladlen Koltun, Micha Sharir
- On average distortion of embedding metrics into the line and into L1by: Yuri Rabinovich
- Cell-probe lower bounds for the partial match problemby: T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani
- On the sample size of k-restricted min-wise independent permutations and other k-wise distributionsby: Toshiya Itoh, Yoshinori Takei, Jun Tarui
- Hidden translation and orbit coset in quantum computingby: Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, Pranab Sen
- Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functionsby: Martin Sauerhoff, Philipp Woelfel
- A new approach to dynamic all pairs shortest pathsby: Camil Demetrescu, Giuseppe F. Italiano
- Lower bounds on the efficiency of encryption and digital signature schemesby: Rosario Gennaro, Yael Gertner, Jonathan Katz
- The online set cover problemby: Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor
- Touring a sequence of polygonsby: Moshe Dror, Alon Efrat, Anna Lubiw, Joseph S. B. Mitchell
- Optimal oblivious routing in polynomial timeby: Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
- Classical deterministic complexity of Edmonds' Problem and quantum entanglementby: Leonid Gurvits
- Reducing truth-telling online mechanisms to online optimizationby: Baruch Awerbuch, Yossi Azar, Adam Meyerson
- Modified log-sobolev inequalities, mixing and hypercontractivityby: Sergey Bobkov, Prasad Tetali
- Better streaming algorithms for clustering problemsby: Moses Charikar, Liadan O'Callaghan, Rina Panigrahy
- Constant factor approximation of vertex-cuts in planar graphsby: Eyal Amir, Robert Krauthgamer, Satish Rao
- Almost random graphs with simple hash functionsby: Martin Dietzfelbinger, Philipp Woelfel
- Approximation schemes for clustering problemsby: Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani
- Derandomizing polynomial identity tests means proving circuit lower boundsby: Valentine Kabanets, Russell Impagliazzo
- A proof of Alon's second eigenvalue conjectureby: Joel Friedman
- Optimal probabilistic fingerprint codesby: Gábor Tardos
- Learning juntasby: Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio
- Extractors: optimal up to constant factorsby: Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, Avi Wigderson
- Space efficient dynamic stabbing with fast queriesby: Mikkel Thorup
- On metric ramsey-type phenomenaby: Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
- Exponential lower bound for 2-query locally decodable codes via a quantum argumentby: Iordanis Kerenidis, Ronald de Wolf
- Boosting in the presence of noiseby: Adam Kalai, Rocco A. Servedio
- Approximation algorithms for hierarchical location problemsby: C. Greg Plaxton
- Randomly coloring graphs of girth at least fiveby: Thomas P. Hayes
- Adiabatic quantum state generation and statistical zero knowledgeby: Dorit Aharonov, Amnon Ta-Shma
- The threshold for random k-SAT is 2k (ln 2 - O(k))by: Dimitris Achlioptas, Yuval Peres
- Consistent load balancing via spread minimizationby: Robert D. Kleinberg, Frank Thomson Leighton
- The Joy of Theoryby: Christos H. Papadimitriou
- Dynamic subgraph connectivity with geometric applicationsby: Timothy M. Chan
- Stability of load balancing algorithms in dynamic adversarial systemsby: Elliot Anshelevich, David Kempe, Jon M. Kleinberg
- The invasiveness of off-line memory checkingby: Miklós Ajtai
- Clairvoyant scheduling of random walksby: Péter Gács
- Improved cryptographic hash functions with worst-case/average-case connectionby: Daniele Micciancio
- The complexity of choosing an H-colouring (nearly) uniformly at randomby: Leslie Ann Goldberg, Steven Kelk, Mike Paterson
- Computing the betti numbers of arrangementsby: Saugata Basu
- Deterministic sorting in O(nlog log n) time and linear spaceby: Yijie Han
- On the complexity of matrix productby: Ran Raz
- Crawling on web graphsby: Colin Cooper, Alan M. Frieze
- The Glauber dynamics on colourings of a graph with high girth and maximum degreeby: Michael Molloy
- Recognizing string graphs in NPby: Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic
- The price of anarchy is independent of the network topologyby: Tim Roughgarden
- Hardness results for approximate hypergraph coloringby: Subhash Khot
- Random sampling and approximation of MAX-CSP problemsby: Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski
- Randomness conductors and constant-degree lossless expandersby: Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson
- Expanders from symmetric codesby: Roy Meshulam, Avi Wigderson
- Fast, small-space algorithms for approximate histogram maintenanceby: Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin Strauss
- Competitive recommendation systemsby: Petros Drineas, Iordanis Kerenidis, Prabhakar Raghavan
- Near-optimal sparse fourier representations via samplingby: Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss
- Equitable cost allocations via primal-dual-type algorithmsby: Kamal Jain, Vijay V. Vazirani
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest pathsby: Surender Baswana, Ramesh Hariharan, Sandeep Sen
- Resolution lower bounds for the weak pigeonhole principleby: Ran Raz
- Competitive generalized auctionsby: Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin
- Optimal finger search trees in the pointer machineby: Gerth Stølting Brodal, George Lagogiannis, Christos Makris, Athanasios K. Tsakalidis, Kostas Tsichlas
- On the advantage over a random assignmentby: Johan Håstad, S. Venkatesh
- Concurrent zero-knowledge with timing, revisitedby: Oded Goldreich
- Tight security proofs for the bounded-storage modelby: Stefan Dziembowski, Ueli M. Maurer
- Universally composable two-party and multi-party secure computationby: Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai
- A new greedy approach for facility location problemsby: Kamal Jain, Mohammad Mahdian, Amin Saberi
- Polynomial-time quantum algorithms for Pell's equation and the principal ideal problemby: Sean Hallgren
- Monotonicity testing over general poset domainsby: Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky
- New results on monotone dualization and generating hypergraph transversalsby: Thomas Eiter, Georg Gottlob, Kazuhisa Makino
- On the complexity of equilibriaby: Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra
- Learnability beyond AC0by: Jeffrey C. Jackson, Adam Klivans, Rocco A. Servedio
- Similarity estimation techniques from rounding algorithmsby: Moses Charikar
- Models and thresholds for random constraint satisfaction problemsby: Michael Molloy
- Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilonby: Jonas Holmerin
- A new average case analysis for completion time schedulingby: Mark Scharbrodt, Thomas Schickinger, Angelika Steger
- Average case analysis for batched disk scheduling and increasing subsequencesby: Eitan Bachmat
- Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabetsby: Venkatesan Guruswami, Piotr Indyk
- Verifying candidate matches in sparse and wildcard matchingby: Richard Cole, Ramesh Hariharan
- On randomized online schedulingby: Susanne Albers
- Hard examples for bounded depth fregeby: Eli Ben-Sasson
- Size space tradeoffs for resolutionby: Eli Ben-Sasson
- Meldable heaps and boolean union-findby: Haim Kaplan, Nira Shafrir, Robert Endre Tarjan
- Fitting algebraic curves to noisy databy: Sanjeev Arora, Subhash Khot
- Approximate clustering via core-setsby: Mihai Badoiu, Sariel Har-Peled, Piotr Indyk
- On the power of unique 2-prover 1-round gamesby: Subhash Khot
- Secure multi-party quantum computationby: Claude Crépeau, Daniel Gottesman, Adam Smith
- Girth and euclidean distortionby: Nathan Linial, Avner Magen, Assaf Naor
- Hardness amplification within NPby: Ryan O'Donnell
- Space lower bounds for distance approximation in the data stream modelby: Michael E. Saks, Xiaodong Sun
- Space-efficient approximate Voronoi diagramsby: Sunil Arya, Theocharis Malamatos, David M. Mount
- Strict polynomial-time in simulation and extractionby: Boaz Barak, Yehuda Lindell
- Wait-free consensus with infinite arrivalsby: James Aspnes, Gauri Shah, Jatin Shah
- Approximating the smallest grammar: Kolmogorov complexity in natural modelsby: Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, April Rasala, Amit Sahai, Abhi Shelat
- Random sampling in residual graphsby: David R. Karger, Matthew S. Levine
- Finding nearest neighbors in growth-restricted metricsby: David R. Karger, Matthias Ruhl
- Algorithmic derandomization via complexity theoryby: D. Sivakumar
- Approximation algorithms for minimum-cost k-vertex connected subgraphsby: Joseph Cheriyan, Santosh Vempala, Adrian Vetta
- Exact learning of DNF formulas using DNF hypothesesby: Lisa Hellerstein, Vijay Raghavan
- Solving convex programs by random walksby: Dimitris Bertsimas, Santosh Vempala
- Relations between average case complexity and approximation complexityby: Uriel Feige
- Reimer's inequality and tardos' conjectureby: Clifford D. Smyth
- Cache-oblivious priority queue and graph algorithm applicationsby: Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro
- Quantum lower bound for the collision problemby: Scott Aaronson
- A polynomial-time algorithm to approximately count contingency tables when the number of rows is constantby: Mary Cryan, Martin E. Dyer
- On the composition of authenticated byzantine agreementby: Yehuda Lindell, Anna Lysyanskaya, Tal Rabin
- Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machinesby: Spyros C. Kontogiannis
- Combinatorial optimization problems in self-assemblyby: Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo Moisset de Espanés, Paul W. K. Rothemund
- An exponential separation between regular and general resolutionby: Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart
- Optimal rate-based scheduling on multiprocessorsby: Anand Srinivasan, James H. Anderson
- 3-manifold knot genus is NP-completby: Ian Agol, Joel Hass, William P. Thurston
- Selfish traffic allocation for server farmsby: Artur Czumaj, Piotr Krysta, Berthold Vöcking
- On communication over an entanglement-assisted quantum channelby: Ashwin Nayak, Julia Salzman
- A unified analysis of hot video schedulersby: Wun-Tat Chan, Tak Wah Lam, Hing-Fung Ting, Prudence W. H. Wong
- Approximation schemes for preemptive weighted flow timeby: Chandra Chekuri, Sanjeev Khanna
- Huffman coding with unequal letter costsby: Mordecai J. Golin, Claire Kenyon, Neal E. Young
- Approximate counting of inversions in a data streamby: Miklós Ajtai, T. S. Jayram, Ravi Kumar, D. Sivakumar
- Combinatorial logarithmic approximation algorithm for directed telephone broadcast problemby: Michael Elkin, Guy Kortsarz
- The importance of being biasedby: Irit Dinur, Shmuel Safra
- On paging with locality of referenceby: Susanne Albers, Lene M. Favrholdt, Oliver Giel
- Clifford algebras and approximating the permanentby: Steve Chien, Lars Eilstrup Rasmussen, Alistair Sinclair
- Tradeoffs in probabilistic packet marking for IP tracebackby: Micah Adler
- Limits to list decodability of linear codesby: Venkatesan Guruswami
- The complexity of approximating entropyby: Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld
- Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problemsby: Paul Beame, Erik Vee
- Pseudo-random generators for all hardnessesby: Christopher Umans
- 2-round zero knowledge and proof auditorsby: Cynthia Dwork, Larry J. Stockmeyer
- Almost all graphs with average degree 4 are 3-colorableby: Dimitris Achlioptas, Cristopher Moore
- Computing crossing numbers in quadratic timeby: Martin Grohe
- Algorithms, games, and the internetby: Christos H. Papadimitriou
- Optimal static range reporting in one dimensionby: Stephen Alstrup, Gerth Stølting Brodal, Theis Rauhe
- Decidability of string graphsby: Marcus Schaefer, Daniel Stefankovic
- Automata, circuits and hybrids: facets of continuous timeby: Boris A. Trakhtenbrot
- Local search heuristic for k-median and facility location problemsby: Vijay Arya, Naveen Garg, Rohit Khandekar, Kamesh Munagala, Vinayaka Pandit
- A read-once branching program lower bound of Omega(2n/4) for integer multiplication using universalby: Beate Bollig, Philipp Woelfel
- Compatible sequences and a slow Winkler percolationby: Péter Gács
- Estimating true evolutionary distances between genomesby: Li-San Wang, Tandy Warnow
- The round complexity of verifiable secret sharing and secure multicastby: Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin
- Quantum walks on graphsby: Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani
- Quantum computers that can be simulated classically in polynomial timeby: Leslie G. Valiant
- Some perspective on computational complexity (abstract)by: Andrew Chi-Chih Yao
- One-dimensional quantum walksby: Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous
- Stackelberg scheduling strategiesby: Tim Roughgarden
- When is the evaluation of conjunctive queries tractable?by: Martin Grohe, Thomas Schwentick, Luc Segoufin
- On the cell probe complexity of membership and perfect hashingby: Rasmus Pagh
- Applications of approximation algorithms to cooperative gamesby: Kamal Jain, Vijay V. Vazirani
- Almost optimal permutation routing on hypercubesby: Berthold Vöcking
- Edge isoperimetry and rapid mixing on matroids and geometric Markov chainsby: Ravi Montenegro, Jung-Bae Son
- Minimax parametric optimization problems and multi-dimensional parametric searchingby: Takeshi Tokuyama
- Lower bounds for matrix product, in bounded depth circuits with arbitrary gatesby: Ran Raz, Amir Shpilka
- Learning DNF in time 2Õ(n1/3)by: Adam Klivans, Rocco A. Servedio
- The complexity of analytic tableauxby: Noriko H. Arai, Toniann Pitassi, Alasdair Urquhart
- Black-box concurrent zero-knowledge requires Omega~(log n) roundsby: Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen
- One line and n pointsby: Bernd Gärtner, József Solymosi, Falk Tschirschnitz, Emo Welzl, Pavel Valtr
- Buffer overflow management in QoS switchesby: Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, Maxim Sviridenko
- Testing of matrix propertiesby: Eldar Fischer, Ilan Newman
- Sparse polynomial approximation in finite fieldsby: Igor Shparlinski
- Optimal outlier removal in high-dimensionalby: John Dunagan, Santosh Vempala
- Interaction in quantum communication and the complexity of set disjointnessby: Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman
- Regular resolution lower bounds for the weak pigeonhole principleby: Toniann Pitassi, Ran Raz
- The price of selfish routingby: Marios Mavronicolas, Paul G. Spirakis
- Colouring graphs when the number of colours is nearly the maximum degreeby: Michael Molloy, Bruce A. Reed
- Explicit lower bound of 4.5n - o(n) for boolena circuitsby: Oded Lachish, Ran Raz
- Data-streams and histogramsby: Sudipto Guha, Nick Koudas, Kyuseok Shim
- A constant factor approximation for the single sink edge installation problemsby: Sudipto Guha, Adam Meyerson, Kamesh Munagala
- Algorithms for minimizing weighted flow timeby: Chandra Chekuri, Sanjeev Khanna, An Zhu
- Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial timeby: Daniel A. Spielman, Shang-Hua Teng
- Non-approximability results for optimization problems on bounded degree instancesby: Luca Trevisan
- Spatial gossip and resource location protocolsby: David Kempe, Jon M. Kleinberg, Alan J. Demers
- Loss-less condensers, unbalanced expanders, and extractorsby: Amnon Ta-Shma, Christopher Umans, David Zuckerman
- Sampling algorithms: lower bounds and applicationsby: Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar
- Fully-dynamic min-cutby: Mikkel Thorup
- On the integrality ratio of semidefinite relaxations of MAX CUTby: Uriel Feige, Gideon Schechtman
- Online server allocation in a server farm via benefit task systemsby: T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko
- Clustering to minimize the sum of cluster diametersby: Moses Charikar, Rina Panigrahy
- Approximating min-sum k-clustering in metric spacesby: Yair Bartal, Moses Charikar, Danny Raz
- A sieve algorithm for the shortest lattice vector problemby: Miklós Ajtai, Ravi Kumar, D. Sivakumar
- Concurrent and resettable zero-knowledge in poly-loalgorithm roundsby: Joe Kilian, Erez Petrank
- Conditions on input vectors for consensus solvability in asynchronous distributed systemsby: Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal
- Quantum mechanical algorithms for the nonabelian hidden subgroup problemby: Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani
- Computing with continuous-time Liapunov systemsby: Jirí Síma, Pekka Orponen
- Spectral analysis of databy: Yossi Azar, Amos Fiat, Anna R. Karlin, Frank McSherry, Jared Saia
- Biased dictionaries with fast insert/deletesby: Funda Ergün, Süleyman Cenk Sahinalp, Jonathan Sharp, Rakesh K. Sinha
- Testing metric propertiesby: Michal Parnas, Dana Ron
- Extractor codesby: Amnon Ta-Shma, David Zuckerman
- Private approximation of NP-hard functionsby: Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim
- A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3Dby: Christian Icking, Lihong Ma
- Quantitative solution of omega-regular gamesby: Luca de Alfaro, Rupak Majumdar
- Dynamic TCP acknowledgement and other stories about e/(e-1)by: Anna R. Karlin, Claire Kenyon, Dana Randall
- Lower bounds for intersection searching and fractional cascading in higher dimensionby: Bernard Chazelle, Ding Liu
- Approximate distance oraclesby: Mikkel Thorup, Uri Zwick
- Running time and program size for self-assembled squaresby: Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang
- The complexity of maximal constraint languagesby: Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons
- Euler paths in series parallel graphsby: S. Rao Kosaraju
- A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entriesby: Mark Jerrum, Alistair Sinclair, Eric Vigoda
- Profit-earning facility locationby: Adam Meyerson
- On optimal slicing of parallel programsby: Markus Müller-Olm, Helmut Seidl
- A new protocol and lower bounds for quantum coin flippingby: Andris Ambainis
- Communication preserving protocols for secure function evaluationby: Moni Naor, Kobbi Nissim
- Anti-presistence: history independent data structuresby: Moni Naor, Vanessa Teague
- Approximation algorithms for constrained for constrained node weighted steiner tree problemsby: Anna Moss, Yuval Rabani
- Randomness efficient identity testing of multivariate polynomialsby: Adam Klivans, Daniel A. Spielman
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programmingby: Michel X. Goemans, David P. Williamson
- A sharp threshold in proof complexityby: Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy
- Complex tilingsby: Bruno Durand, Leonid A. Levin, Alexander Shen
- Excellent codes from modular curvesby: Noam D. Elkies
- Sharp threshold and scaling window for the integer partitioning problemby: Christian Borgs, Jennifer T. Chayes, Boris Pittel
- (1+epsilon, beta)-spanner constructions for general graphsby: Michael Elkin, David Peleg
- Learning mixtures of arbitrary gaussiansby: Sanjeev Arora, Ravi Kannan
- Non-clairvoyant scheduling to minimize the average flow time on single and parallel machinesby: Luca Becchetti, Stefano Leonardi
- Distribution functions of probabilistic automataby: Farrokh Vatan
- Provisioning a virtual private network: a network design problem for multicommodity flowby: Anupam Gupta, Jon M. Kleinberg, Amit Kumar, Rajeev Rastogi, Bülent Yener
- Fast computation of low rank matrixby: Dimitris Achlioptas, Frank McSherry
- Quantum algorithms for solvable groupsby: John Watrous
- Isomorphism testing for embeddable graphs through definabilityby: Martin Grohe
- On the approximability of the traveling salesman problem (extended abstract)by: Christos H. Papadimitriou, Santosh Vempala
- Higher lower bounds on monotone sizeby: Danny Harnik, Ran Raz
- Rapid sampling though quantum computingby: Lov K. Grover
- More general completeness theorems for secure two-party computationby: Joe Kilian
- Computing with highly mixed states (extended abstract)by: Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani
- Finding long paths and cycles in sparse Hamiltonian graphsby: Tomás Feder, Rajeev Motwani, Carlos S. Subi
- The program-size complexity of self-assembled squares (extended abstract)by: Paul W. K. Rothemund, Erik Winfree
- Normal subgroup reconstruction and quantum computation using group representationsby: Sean Hallgren, Alexander Russell, Amnon Ta-Shma
- A matter of degree: improved approximation algorithms for degree-bounded minimum spanning treesby: Jochen Könemann, R. Ravi
- Near optimal multiple alignment within a band in polynomial timeby: Ming Li, Bin Ma, Lusheng Wang
- Matrix-vector product for confluent Cauchy-like matrices with application to confluent rational interpolationby: Vadim Olshevsky, Mohammad Amin Shokrollahi
- From partial consistency to global broadcastby: Matthias Fitzi, Ueli M. Maurer
- Clustering for edge-cost minimization (extended abstract)by: Leonard J. Schulman
- Randomized metarounding (extended abstract)by: Robert D. Carr, Santosh Vempala
- Approximate nearest neighbors and sequence comparison with block operationsby: S. Muthukrishnan, Süleyman Cenk Sahinalp
- How tall is a tree?by: Bruce A. Reed
- Noise-tolerant learning, the parity problem, and the statistical query modelby: Avrim Blum, Adam Kalai, Hal Wasserman
- Finding smooth integers in short intervals using CRT decodingby: Dan Boneh
- Resettable zero-knowledge (extended abstract)by: Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali
- On dual minimum cost flow algorithms (extended abstract)by: Jens Vygen
- Improved approximations of crossings in graph drawingsby: Guy Even, Sudipto Guha, Baruch Schieber
- Shortest path queries in planar graphsby: Danny Z. Chen, Jinhui Xu
- On the decidability of accessibility problems (extended abstract)by: Rajeev Motwani, Rina Panigrahy, Vijay A. Saraswat, Suresh Ventkatasubramanian
- A guessing game and randomized online algorithmsby: Steven S. Seiden
- epsilon-optimization schemes and L-bit precision: alternative perspectives in combinatorial optimization (extended abstract)by: James B. Orlin, Andreas S. Schulz, Sudipta Sengupta
- On the complexity of verifiable secret sharing and multiparty computationby: Ronald Cramer, Ivan Damgård, Stefan Dziembowski
- A unified approach to approximating resource allocation and schedulingby: Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, Baruch Schieber
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)by: Roberto Grossi, Jeffrey Scott Vitter
- Exact computations of the inertia symmetric integer matricesby: Steven Fortune
- The value of strong inapproximability results for cliqueby: Aravind Srinivasan
- Compression using efficient multicastingby: Micah Adler, Frank Thomson Leighton
- The risk profile problem for stock portfolio optimization (extended abstract)by: Ming-Yang Kao, Andreas Nolte, Stephen R. Tate
- On quantum and probabilistic communication: Las Vegas and one-way protocolsby: Hartmut Klauck
- List decoding algorithms for certain concatenated codesby: Venkatesan Guruswami, Madhu Sudan
- On the efficiency of local decoding procedures for error-correcting codesby: Jonathan Katz, Luca Trevisan
- Complete characterization of security notions for probabilistic private-key encryptionby: Jonathan Katz, Moti Yung
- Faster suffix tree construction with missing suffix linksby: Richard Cole, Ramesh Hariharan
- More theory revision with queries (extended abstract)by: Judy Goldsmith, Robert H. Sloan
- Connectivity and inference problems for temporal networksby: David Kempe, Jon M. Kleinberg, Amit Kumar
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functionsby: Satoru Iwata, Lisa Fleischer, Satoru Fujishige
- Near-optimal fully-dynamic graph connectivityby: Mikkel Thorup
- Combining fairness with throughput: online routing with multiple objectivesby: Ashish Goel, Adam Meyerson, Serge A. Plotkin
- On transformation of interactive proofs that preserve the prover's complexityby: Salil P. Vadhan
- Polynomial-time approximation scheme for data broadcastby: Claire Kenyon, Nicolas Schabanel, Neal E. Young
- Balanced allocations: the heavily loaded caseby: Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vöcking
- A constant factor approximation algorithm for a class of classification problemsby: Anupam Gupta, Éva Tardos
- A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)by: Meena Mahajan, Kasturi R. Varadarajan
- On the sum-of-squares algorithm for bin packingby: János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
- A PCP characterization of NP with optimal amortized query complexityby: Alex Samorodnitsky, Luca Trevisan
- Tighter bounds for nearest neighbor search and related problems in the cell probe modelby: Omer Barkol, Yuval Rabani
- Parallelization, amplification, and exponential time simulation of quantum interactive proof systemsby: Alexei Kitaev, John Watrous
- A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)by: Artur Czumaj, Christian Scheideler
- Quantum bit escrowby: Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao
- Query strategies for priced information (extended abstract)by: Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai
- A deterministic polynomial-time algorithm for approximating mixed disc
