ACM Symposium on Theory of Computing

The Digital Librarian's Digital Library

DOCIS Documents in Computing and Information Science

Home >> Journals and Conference Proceedings

ACM Symposium on Theory of Computing

2005

Spectral norm of random matrices
by: Van H. Vu
The complexity of agreement
by: Scott Aaronson
Testing versus estimation of graph properties
by: Eldar Fischer, Ilan Newman
Hardness of the undirected edge-disjoint paths problem
by: Matthew Andrews, Lisa Zhang
Fast quantum algorithms for computing the unit group and class group of a number field
by: Sean Hallgren
Key agreement from weak bit agreement
by: Thomas Holenstein
Hierarchies for semantic classes
by: Lance Fortnow, Rahul Santhanam, Luca Trevisan
Approximately counting integral flows and cell-bounded contingency tables
by: Mary Cryan, Martin E. Dyer, Dana Randall
Convex programming for scheduling unrelated parallel machines
by: Yossi Azar, Amir Epstein
Edge partition of planar sraphs into two outerplanar graphs
by: Daniel Gonçalves
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
by: Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis
Lower bounds for k-DNF resolution on random 3-CNFs
by: Michael Alekhnovich
Computing correlated equilibria in multi-player games
by: Christos H. Papadimitriou
Improved approximation algorithms for minimum-weight vertex separators
by: Uriel Feige, Mohammad Taghi Hajiaghayi, James R. Lee
An O(log n log log n) space algorithm for undirected st-connectivity
by: Vladimir Trifonov
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
by: Zeev Dvir, Amir Shpilka
Derandomization of auctions
by: 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 agreement
by: Eli Gafni, Rachid Guerraoui, Bastian Pochon
Learning nonsingular phylogenies and hidden Markov models
by: Elchanan Mossel, Sébastien Roch
On strip packing With rotations
by: Klaus Jansen, Rob van Stee
An optimal multi-writer snapshot algorithm
by: Prasad Jayanti
The mixing time of the Thorp shuffle
by: Ben Morris
Covert two-party computation
by: Luis von Ahn, Nicholas J. Hopper, John Langford
Hardness of the undirected congestion minimization problem
by: Matthew Andrews, Lisa Zhang
Quadratic forms on graphs
by: Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
Cooperative asynchronous update of shared memory
by: Bogdan S. Chlebus, Dariusz R. Kowalski
Lower-stretch spanning trees
by: Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng
On non-uniform multicommodity buy-at-bulk network design
by: Moses Charikar, Adriana Karagiozova
Beyond NP: the work and legacy of Larry Stockmeyer
by: Lance Fortnow
New and improved constructions of non-malleable cryptographic protocols
by: Rafael Pass, Alon Rosen
Bounded-depth circuits: separating wires from gates
by: Michal Koucký, Pavel Pudlák, Denis Thérien
Market equilibrium via the excess demand function
by: Bruno Codenotti, Benton McCune, Kasturi R. Varadarajan
Tree-walking automata do not recognize all regular languages
by: Mikolaj Bojanczyk, Thomas Colcombet
Correcting errors without leaking partial information
by: Yevgeniy Dodis, Adam Smith
Large the price of routing unsplittable flow
by: Baruch Awerbuch, Yossi Azar, Amir Epstein
Approximation techniques for utilitarian mechanism design
by: Patrick Briest, Piotr Krysta, Berthold Vöcking
Testing monotone high-dimensional distributions
by: Ronitt Rubinfeld, Rocco A. Servedio
Optimal approximations of the frequency moments of data streams
by: Piotr Indyk, David P. Woodruff
Multicommodity flow, well-linked terminals, and routing problems
by: Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
Tensor decomposition and approximation schemes for constraint satisfaction problems
by: Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh Vempala
Limits to list decoding Reed-Solomon codes
by: Venkatesan Guruswami, Atri Rudra
Pseudorandom generators for low degree polynomials
by: Andrej Bogdanov
Extractors with weak random seeds
by: Ran Raz
Saving an epsilon: a 2-approximation for the k-MST problem in graphs
by: Naveen Garg
Learning with attribute costs
by: Haim Kaplan, Eyal Kushilevitz, Yishay Mansour
Tensor norms and the classical communication complexity of nonlocal quantum measurement
by: Yaoyun Shi
Aggregating inconsistent information: ranking and clustering
by: Nir Ailon, Moses Charikar, Alantha Newman
The price of anarchy of finite congestion games
by: George Christodoulou, Elias Koutsoupias
Approximation algorithms for combinatorial auctions with complement-free bidders
by: Shahar Dobzinski, Noam Nisan, Michael Schapira
Euclidean distortion and the sparsest cut
by: Sanjeev Arora, James R. Lee, Assaf Naor
On uniform amplification of hardness in NP
by: Luca Trevisan
On the bias of traceroute sampling: or, power-law degree distributions in regular graphs
by: Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore
On algorithms for discrete and approximate brouwer fixed points
by: Xi Chen, Xiaotie Deng
Every monotone graph property is testable
by: Noga Alon, Asaf Shapira
On random pm 1 matrices: singularity and determinant
by: Terence Tao, Van H. Vu
Balanced metric labeling
by: Joseph Naor, Roy Schwartz
Simple PCPs with poly-log rate and query complexity
by: Eli Ben-Sasson, Madhu Sudan
Undirected ST-connectivity in log-space
by: Omer Reingold
On obfuscating point functions
by: Hoeteck Wee
Collusion-free protocols
by: Matt Lepinski, Silvio Micali, Abhi Shelat
O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
by: 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 cryptography
by: Oded Regev
Low-distortion embeddings of general metrics into the line
by: Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos
Towards asymptotic optimality in probabilistic packet marking
by: Micah Adler, Jeff Edmonds, Jirí Matousek
Efficient testing of groups
by: Katalin Friedl, Gábor Ivanyos, Miklos Santha
Oblivious routing in directed graphs with random demands
by: Mohammad Taghi Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Räcke
Representing hard lattices with O(n log n) bits
by: Miklós Ajtai
Worst-case update times for fully-dynamic all-pairs shortest paths
by: Mikkel Thorup
Universal approximations for TSP, Steiner tree, and set cover
by: Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, Ravi Sundaram
Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors
by: Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson
Coresets in dynamic geometric data streams
by: Gereon Frahling, Christian Sohler
Computing the first Betti number and the connected components of semi-algebraic sets
by: Saugata Basu, Richard Pollack, Marie-Françoise Roy
Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities
by: Saugata Basu
Low distortion embeddings for edit distance
by: Rafail Ostrovsky, Yuval Rabani
The round complexity of two-party random selection
by: Saurabh Sanghvi, Salil P. Vadhan
A new strategy for querying priced information
by: Ferdinando Cicalese, Eduardo Sany Laber
Every 2-CSP allows nontrivial approximation
by: Johan Håstad
Approximation algorithms for network design with metric costs
by: Joseph Cheriyan, Adrian Vetta
Concurrent general composition of secure protocols in the timing model
by: Yael Tauman Kalai, Yehuda Lindell, Manoj Prabhakaran
On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem
by: Abraham Flaxman, Alan M. Frieze, Juan C. Vera
On dynamic range reporting in one dimension
by: Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu
Polynomial time quantum algorithm for the computation of the unit group of a number field
by: Arthur Schmidt, Ulrich Vollmer
Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read
by: Itai Benjamini, Oded Schramm, David B. Wilson
Fast quantum byzantine agreement
by: Michael Ben-Or, Avinatan Hassidim

2004

Multi-linear formulas for permanent and determinant are of super-polynomial size
by: Ran Raz
Completeness in two-party secure computation: a computational view
by: Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen
A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
by: Jonas Holmerin, Subhash Khot
Sharp thresholds For monotone properties in random geometric graphs
by: Ashish Goel, Sanatan Rai, Bhaskar Krishnamachari
A decentralized algorithm for spectral analysis
by: David Kempe, Frank McSherry
The difficulty of testing for isomorphism against a graph that is given in advance
by: Eldar Fischer
Linear FPT reductions and computational lower bounds
by: Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia
Quantum and classical query complexities of local search are polynomially related
by: Miklos Santha, Mario Szegedy
Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks
by: Gurmeet Singh Manku, Moni Naor, Udi Wieder
Multilinear formulas and skepticism of quantum computing
by: Scott Aaronson
Using nondeterminism to amplify hardness
by: Alexander Healy, Salil P. Vadhan, Emanuele Viola
Quantum algorithms a decade after shor
by: 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 genus
by: Jonathan A. Kelner
Batch codes and their applications
by: Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Auction algorithms for market equilibrium
by: Rahul Garg, Sanjiv Kapoor
Exponential separation of quantum and classical one-way communication complexity
by: Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis
On sums of independent random variables with unbounded variance, and estimating the average degree in a graph
by: Uriel Feige
Dictionary matching and indexing with errors and don't cares
by: Richard Cole, Lee-Ad Gottlieb, Moshe Lewenstein
An approximate König's theorem for edge-coloring weighted bipartite graphs
by: José R. Correa, Michel X. Goemans
The all-or-nothing multicommodity flow problem
by: Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
Adaptive routing with end-to-end feedback: distributed learning and geometric approaches
by: Baruch Awerbuch, Robert D. Kleinberg
On coresets for k-means and k-median clustering
by: Sariel Har-Peled, Soham Mazumdar
The quantum adiabatic optimization algorithm and local minima
by: Ben Reichardt
Algorithms for dynamic geometric problems over data streams
by: Piotr Indyk
Approximation algorithms for deadline-TSP and vehicle routing with time-windows
by: Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson
Sublinear algorithms for testing monotone and unimodal distributions
by: Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld
A simple polynomial-time rescaling algorithm for solving linear programs
by: John Dunagan, Santosh Vempala
Computing Nash equilibria for scheduling on restricted parallel links
by: Martin Gairing, Thomas Lücking, Marios Mavronicolas, Burkhard Monien
New hardness results for congestion minimization and machine scheduling
by: Julia Chuzhoy, Joseph Naor
Estimating the weight of metric minimum spanning trees in sublinear-time
by: Artur Czumaj, Christian Sohler
Bounded-concurrent secure multi-party computation with a dishonest majority
by: Rafael Pass
Typical properties of winners and losers in discrete optimization
by: René Beier, Berthold Vöcking
Solving fractional packing problems in Oast(1/?) iterations
by: Daniel Bienstock, Garud Iyengar
Asymmetric k-center is log* n-hard to approximate
by: Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor
Low distortion maps between point sets
by: Claire Kenyon, Yuval Rabani, Alistair Sinclair
Bypassing the embedding: algorithms for low dimensional metrics
by: Kunal Talwar
Finding paths and cycles of superpolylogarithmic length
by: Harold N. Gabow
The zero-one principle for switching networks
by: Yossi Azar, Yossi Richter
Using mixture models for collaborative filtering
by: Jon M. Kleinberg, Mark Sandler
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
by: Daniel A. Spielman, Shang-Hua Teng
Multi-processor scheduling to minimize flow time with epsilon resource augmentation
by: Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar
Collective asynchronous reading with polylogarithmic worst-case overhead
by: Bogdan S. Chlebus, Dariusz R. Kowalski, Alexander A. Shvartsman
Derandomizing homomorphism testing in general groups
by: Amir Shpilka, Avi Wigderson
Boosted sampling: approximation algorithms for stochastic optimization
by: Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha
The complexity of pure Nash equilibria
by: Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar
A fully dynamic reachability algorithm for directed graphs with an almost linear update time
by: Liam Roditty, Uri Zwick
The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results
by: Nikhil R. Devanur
(Almost) tight bounds and existence theorems for confluent flows
by: Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta
Approximate max-integral-flow/min-multicut theorems
by: Kenji Obata
Graph entropy and quantum sorting problems
by: Andrew Chi-Chih Yao
New notions of security: achieving universal composability without trusted setup
by: Manoj Prabhakaran, Amit Sahai
Primal-dual algorithms for deterministic inventory problems
by: Retsef Levi, Robin Roundy, David B. Shmoys
Lower bounds for linear degeneracy testing
by: Nir Ailon, Bernard Chazelle
Approximation algorithm for k-node connected subgraphs via critical graphs
by: Guy Kortsarz, Zeev Nutov
On the performance of greedy algorithms in packet buffering
by: Susanne Albers, Markus Schmidt
Counting complexity classes for numeric computations II: algebraic and semialgebraic sets
by: Peter Bürgisser, Felipe Cucker
Rational secret sharing and multiparty computation: extended abstract
by: Joseph Y. Halpern, Vanessa Teague
Hit-and-run from a corner
by: László Lovász, Santosh Vempala
Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
by: Michael Elkin
Visibly pushdown languages
by: Rajeev Alur, P. Madhusudan
The two possible values of the chromatic number of a random graph
by: Dimitris Achlioptas, Assaf Naor
Robust pcps of proximity, shorter pcps and applications to coding
by: Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan
Lower bounds for dynamic connectivity
by: Mihai Patrascu, Erik D. Demaine
Depth through breadth, or why should we attend talks in other areas?
by: Avi Wigderson
Network games
by: Éva Tardos
A conjecture about polynomial time computable lattice-lattice functions
by: Miklós Ajtai
Better extractors for better codes?
by: Venkatesan Guruswami
Approximating the cut-norm via Grothendieck's inequality
by: Noga Alon, Assaf Naor
Isotopic implicit surface meshing
by: Jean-Daniel Boissonnat, David Cohen-Steiner, Gert Vegter
Expander flows, geometric embeddings and graph partitioning
by: Sanjeev Arora, Satish Rao, Umesh V. Vazirani
Lower bounds for local search by quantum arguments
by: Scott Aaronson

2003

The computational complexity of some julia sets
by: Robert Rettinger, Klaus Weihrauch
On the power of quantum fingerprinting
by: Andrew Chi-Chih Ya
The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice
by: Miklós Ajtai
Polylogarithmic inapproximability
by: Eran Halperin, Robert Krauthgamer
Meet and merge: approximation algorithms for confluent flows
by: Jiangzhuo Chen, Rajmohan Rajaraman, Ravi Sundaram
Testing subgraphs in directed graphs
by: Noga Alon, Asaf Shapira
Work-competitive scheduling for cooperative computing with dynamic groups
by: Chryssis Georgiou, Alexander Russell, Alexander A. Shvartsman
Sublinear geometric algorithms
by: Bernard Chazelle, Ding Liu, Avner Magen
Random knapsack in expected polynomial time
by: René Beier, Berthold Vöcking
Non-interactive and reusable non-malleable commitment schemes
by: Ivan Damgård, Jens Groth
Approximate counting by dynamic programming
by: Martin E. Dyer
Distinct distances in three and higher dimensions
by: Boris Aronov, János Pach, Micha Sharir, Gábor Tardos
Lower bounds on the amount of randomness in private computation
by: Anna Gál, Adi Rosén
Well-separated pair decomposition for the unit-disk graph metric and its applications
by: Jie Gao, Li Zhang
On the fractal behavior of TCP
by: Anna C. Gilbert, Howard J. Karloff
Server scheduling in the Lp norm: a rising tide lifts all boat
by: Nikhil Bansal, Kirk Pruhs
Short path queries in planar graphs in constant time
by: Lukasz Kowalik, Maciej Kurowski
Uniform hashing in constant time and linear space
by: Anna Östlin, Rasmus Pagh
Generating random regular graphs
by: Jeong Han Kim, Van H. Vu
Sampling lower bounds via information theory
by: Ziv Bar-Yossef
Pricing network edges for heterogeneous selfish users
by: Richard Cole, Yevgeniy Dodis, Tim Roughgarden
Primal-dual meets local search: approximating MST's with nonuniform degree bounds
by: Jochen Könemann, R. Ravi
Reconstructing curves in three (and higher) dimensional space from noisy data
by: Don Coppersmith, Madhu Sudan
A sublinear algorithm for weakly approximating edit distance
by: Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami
A tight bound on approximating arbitrary metrics by tree metrics
by: Jittat Fakcharoenphol, Satish Rao, Kunal Talwar
Some 3CNF properties are hard to test
by: Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova
Exponential algorithmic speedup by a quantum walk
by: Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman
Management of multi-queue switches in QoS networks
by: Yossi Azar, Yossi Richter
Near-optimal network design with selfish agents
by: Elliot Anshelevich, Anirban Dasgupta, Éva Tardos, Tom Wexler
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
by: Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson
Simpler and better approximation algorithms for network design
by: Anupam Gupta, Amit Kumar, Tim Roughgarden
Evolving sets and mixin
by: Ben Morris, Yuval Peres
On the limits of cache-obliviousness
by: Gerth Stølting Brodal, Rolf Fagerberg
A tight time lower bound for space-optimal implementations of multi-writer snapshots
by: Panagiota Fatourou, Faith E. Fich, Eric Ruppert
A stochastic process on the hypercube with applications to peer-to-peer networks
by: Micah Adler, Eran Halperin, Richard M. Karp, Vijay V. Vazirani
Bounded-concurrent secure two-party computation without setup assumptions
by: Yehuda Lindell
OPT versus LOAD in dynamic storage allocation
by: Adam L. Buchsbaum, Howard J. Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup
Quantum time-space tradeoffs for sorting
by: Hartmut Klauck
Linear time encodable and list decodable codes
by: Venkatesan Guruswami, Piotr Indyk
The intrinsic dimensionality of graphs
by: Robert Krauthgamer, James R. Lee
New degree bounds for polynomial threshold functions
by: Ryan O'Donnell, Rocco A. Servedio
A fast algorithm for computing steiner edge connectivity
by: Richard Cole, Ramesh Hariharan
Alpha-shapes and flow shapes are homotopy equivalent
by: Tamal K. Dey, Joachim Giesen, Matthias John
Dynamic rectangular intersection with priorities
by: Haim Kaplan, Eyal Molad, Robert Endre Tarjan
A new multilayered PCP and the hardness of hypergraph vertex cover
by: Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
Two applications of information complexity
by: T. S. Jayram, Ravi Kumar, D. Sivakumar
New lattice based cryptographic constructions
by: Oded Regev
Integer priority queues with decrease key in constant time and the single source shortest paths problem
by: Mikkel Thorup
Cutting triangular cycles of lines in space
by: Boris Aronov, Vladlen Koltun, Micha Sharir
On average distortion of embedding metrics into the line and into L1
by: Yuri Rabinovich
Cell-probe lower bounds for the partial match problem
by: T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani
On the sample size of k-restricted min-wise independent permutations and other k-wise distributions
by: Toshiya Itoh, Yoshinori Takei, Jun Tarui
Hidden translation and orbit coset in quantum computing
by: 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 functions
by: Martin Sauerhoff, Philipp Woelfel
A new approach to dynamic all pairs shortest paths
by: Camil Demetrescu, Giuseppe F. Italiano
Lower bounds on the efficiency of encryption and digital signature schemes
by: Rosario Gennaro, Yael Gertner, Jonathan Katz
The online set cover problem
by: Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor
Touring a sequence of polygons
by: Moshe Dror, Alon Efrat, Anna Lubiw, Joseph S. B. Mitchell
Optimal oblivious routing in polynomial time
by: Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
Classical deterministic complexity of Edmonds' Problem and quantum entanglement
by: Leonid Gurvits
Reducing truth-telling online mechanisms to online optimization
by: Baruch Awerbuch, Yossi Azar, Adam Meyerson
Modified log-sobolev inequalities, mixing and hypercontractivity
by: Sergey Bobkov, Prasad Tetali
Better streaming algorithms for clustering problems
by: Moses Charikar, Liadan O'Callaghan, Rina Panigrahy
Constant factor approximation of vertex-cuts in planar graphs
by: Eyal Amir, Robert Krauthgamer, Satish Rao
Almost random graphs with simple hash functions
by: Martin Dietzfelbinger, Philipp Woelfel
Approximation schemes for clustering problems
by: Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani
Derandomizing polynomial identity tests means proving circuit lower bounds
by: Valentine Kabanets, Russell Impagliazzo
A proof of Alon's second eigenvalue conjecture
by: Joel Friedman
Optimal probabilistic fingerprint codes
by: Gábor Tardos
Learning juntas
by: Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio
Extractors: optimal up to constant factors
by: Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, Avi Wigderson
Space efficient dynamic stabbing with fast queries
by: Mikkel Thorup
On metric ramsey-type phenomena
by: Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
Exponential lower bound for 2-query locally decodable codes via a quantum argument
by: Iordanis Kerenidis, Ronald de Wolf
Boosting in the presence of noise
by: Adam Kalai, Rocco A. Servedio
Approximation algorithms for hierarchical location problems
by: C. Greg Plaxton
Randomly coloring graphs of girth at least five
by: Thomas P. Hayes
Adiabatic quantum state generation and statistical zero knowledge
by: 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 minimization
by: Robert D. Kleinberg, Frank Thomson Leighton

2002

The Joy of Theory
by: Christos H. Papadimitriou
Dynamic subgraph connectivity with geometric applications
by: Timothy M. Chan
Stability of load balancing algorithms in dynamic adversarial systems
by: Elliot Anshelevich, David Kempe, Jon M. Kleinberg
The invasiveness of off-line memory checking
by: Miklós Ajtai
Clairvoyant scheduling of random walks
by: Péter Gács
Improved cryptographic hash functions with worst-case/average-case connection
by: Daniele Micciancio
The complexity of choosing an H-colouring (nearly) uniformly at random
by: Leslie Ann Goldberg, Steven Kelk, Mike Paterson
Computing the betti numbers of arrangements
by: Saugata Basu
Deterministic sorting in O(nlog log n) time and linear space
by: Yijie Han
On the complexity of matrix product
by: Ran Raz
Crawling on web graphs
by: Colin Cooper, Alan M. Frieze
The Glauber dynamics on colourings of a graph with high girth and maximum degree
by: Michael Molloy
Recognizing string graphs in NP
by: Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic
The price of anarchy is independent of the network topology
by: Tim Roughgarden
Hardness results for approximate hypergraph coloring
by: Subhash Khot
Random sampling and approximation of MAX-CSP problems
by: Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski
Randomness conductors and constant-degree lossless expanders
by: Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson
Expanders from symmetric codes
by: Roy Meshulam, Avi Wigderson
Fast, small-space algorithms for approximate histogram maintenance
by: Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin Strauss
Competitive recommendation systems
by: Petros Drineas, Iordanis Kerenidis, Prabhakar Raghavan
Near-optimal sparse fourier representations via sampling
by: Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss
Equitable cost allocations via primal-dual-type algorithms
by: Kamal Jain, Vijay V. Vazirani
Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
by: Surender Baswana, Ramesh Hariharan, Sandeep Sen
Resolution lower bounds for the weak pigeonhole principle
by: Ran Raz
Competitive generalized auctions
by: Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin
Optimal finger search trees in the pointer machine
by: Gerth Stølting Brodal, George Lagogiannis, Christos Makris, Athanasios K. Tsakalidis, Kostas Tsichlas
On the advantage over a random assignment
by: Johan Håstad, S. Venkatesh
Concurrent zero-knowledge with timing, revisited
by: Oded Goldreich
Tight security proofs for the bounded-storage model
by: Stefan Dziembowski, Ueli M. Maurer
Universally composable two-party and multi-party secure computation
by: Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai
A new greedy approach for facility location problems
by: Kamal Jain, Mohammad Mahdian, Amin Saberi
Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
by: Sean Hallgren
Monotonicity testing over general poset domains
by: Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky
New results on monotone dualization and generating hypergraph transversals
by: Thomas Eiter, Georg Gottlob, Kazuhisa Makino
On the complexity of equilibria
by: Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra
Learnability beyond AC0
by: Jeffrey C. Jackson, Adam Klivans, Rocco A. Servedio
Similarity estimation techniques from rounding algorithms
by: Moses Charikar
Models and thresholds for random constraint satisfaction problems
by: Michael Molloy
Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilon
by: Jonas Holmerin
A new average case analysis for completion time scheduling
by: Mark Scharbrodt, Thomas Schickinger, Angelika Steger
Average case analysis for batched disk scheduling and increasing subsequences
by: Eitan Bachmat
Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets
by: Venkatesan Guruswami, Piotr Indyk
Verifying candidate matches in sparse and wildcard matching
by: Richard Cole, Ramesh Hariharan
On randomized online scheduling
by: Susanne Albers
Hard examples for bounded depth frege
by: Eli Ben-Sasson
Size space tradeoffs for resolution
by: Eli Ben-Sasson
Meldable heaps and boolean union-find
by: Haim Kaplan, Nira Shafrir, Robert Endre Tarjan
Fitting algebraic curves to noisy data
by: Sanjeev Arora, Subhash Khot
Approximate clustering via core-sets
by: Mihai Badoiu, Sariel Har-Peled, Piotr Indyk
On the power of unique 2-prover 1-round games
by: Subhash Khot
Secure multi-party quantum computation
by: Claude Crépeau, Daniel Gottesman, Adam Smith
Girth and euclidean distortion
by: Nathan Linial, Avner Magen, Assaf Naor
Hardness amplification within NP
by: Ryan O'Donnell
Space lower bounds for distance approximation in the data stream model
by: Michael E. Saks, Xiaodong Sun
Space-efficient approximate Voronoi diagrams
by: Sunil Arya, Theocharis Malamatos, David M. Mount
Strict polynomial-time in simulation and extraction
by: Boaz Barak, Yehuda Lindell
Wait-free consensus with infinite arrivals
by: James Aspnes, Gauri Shah, Jatin Shah
Approximating the smallest grammar: Kolmogorov complexity in natural models
by: Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, April Rasala, Amit Sahai, Abhi Shelat
Random sampling in residual graphs
by: David R. Karger, Matthew S. Levine
Finding nearest neighbors in growth-restricted metrics
by: David R. Karger, Matthias Ruhl
Algorithmic derandomization via complexity theory
by: D. Sivakumar
Approximation algorithms for minimum-cost k-vertex connected subgraphs
by: Joseph Cheriyan, Santosh Vempala, Adrian Vetta
Exact learning of DNF formulas using DNF hypotheses
by: Lisa Hellerstein, Vijay Raghavan
Solving convex programs by random walks
by: Dimitris Bertsimas, Santosh Vempala
Relations between average case complexity and approximation complexity
by: Uriel Feige
Reimer's inequality and tardos' conjecture
by: Clifford D. Smyth
Cache-oblivious priority queue and graph algorithm applications
by: Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro
Quantum lower bound for the collision problem
by: Scott Aaronson
A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
by: Mary Cryan, Martin E. Dyer
On the composition of authenticated byzantine agreement
by: Yehuda Lindell, Anna Lysyanskaya, Tal Rabin
Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines
by: Spyros C. Kontogiannis
Combinatorial optimization problems in self-assembly
by: 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 resolution
by: Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart
Optimal rate-based scheduling on multiprocessors
by: Anand Srinivasan, James H. Anderson
3-manifold knot genus is NP-complet
by: Ian Agol, Joel Hass, William P. Thurston
Selfish traffic allocation for server farms
by: Artur Czumaj, Piotr Krysta, Berthold Vöcking
On communication over an entanglement-assisted quantum channel
by: Ashwin Nayak, Julia Salzman
A unified analysis of hot video schedulers
by: Wun-Tat Chan, Tak Wah Lam, Hing-Fung Ting, Prudence W. H. Wong
Approximation schemes for preemptive weighted flow time
by: Chandra Chekuri, Sanjeev Khanna
Huffman coding with unequal letter costs
by: Mordecai J. Golin, Claire Kenyon, Neal E. Young
Approximate counting of inversions in a data stream
by: Miklós Ajtai, T. S. Jayram, Ravi Kumar, D. Sivakumar
Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem
by: Michael Elkin, Guy Kortsarz
The importance of being biased
by: Irit Dinur, Shmuel Safra
On paging with locality of reference
by: Susanne Albers, Lene M. Favrholdt, Oliver Giel
Clifford algebras and approximating the permanent
by: Steve Chien, Lars Eilstrup Rasmussen, Alistair Sinclair
Tradeoffs in probabilistic packet marking for IP traceback
by: Micah Adler
Limits to list decodability of linear codes
by: Venkatesan Guruswami
The complexity of approximating entropy
by: Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld
Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
by: Paul Beame, Erik Vee
Pseudo-random generators for all hardnesses
by: Christopher Umans
2-round zero knowledge and proof auditors
by: Cynthia Dwork, Larry J. Stockmeyer
Almost all graphs with average degree 4 are 3-colorable
by: Dimitris Achlioptas, Cristopher Moore

2001

Computing crossing numbers in quadratic time
by: Martin Grohe
Algorithms, games, and the internet
by: Christos H. Papadimitriou
Optimal static range reporting in one dimension
by: Stephen Alstrup, Gerth Stølting Brodal, Theis Rauhe
Decidability of string graphs
by: Marcus Schaefer, Daniel Stefankovic
Automata, circuits and hybrids: facets of continuous time
by: Boris A. Trakhtenbrot
Local search heuristic for k-median and facility location problems
by: 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 universal
by: Beate Bollig, Philipp Woelfel
Compatible sequences and a slow Winkler percolation
by: Péter Gács
Estimating true evolutionary distances between genomes
by: Li-San Wang, Tandy Warnow
The round complexity of verifiable secret sharing and secure multicast
by: Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin
Quantum walks on graphs
by: Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani
Quantum computers that can be simulated classically in polynomial time
by: Leslie G. Valiant
Some perspective on computational complexity (abstract)
by: Andrew Chi-Chih Yao
One-dimensional quantum walks
by: Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous
Stackelberg scheduling strategies
by: 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 hashing
by: Rasmus Pagh
Applications of approximation algorithms to cooperative games
by: Kamal Jain, Vijay V. Vazirani
Almost optimal permutation routing on hypercubes
by: Berthold Vöcking
Edge isoperimetry and rapid mixing on matroids and geometric Markov chains
by: Ravi Montenegro, Jung-Bae Son
Minimax parametric optimization problems and multi-dimensional parametric searching
by: Takeshi Tokuyama
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
by: Ran Raz, Amir Shpilka
Learning DNF in time 2Õ(n1/3)
by: Adam Klivans, Rocco A. Servedio
The complexity of analytic tableaux
by: Noriko H. Arai, Toniann Pitassi, Alasdair Urquhart
Black-box concurrent zero-knowledge requires Omega~(log n) rounds
by: Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen
One line and n points
by: Bernd Gärtner, József Solymosi, Falk Tschirschnitz, Emo Welzl, Pavel Valtr
Buffer overflow management in QoS switches
by: Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, Maxim Sviridenko
Testing of matrix properties
by: Eldar Fischer, Ilan Newman
Sparse polynomial approximation in finite fields
by: Igor Shparlinski
Optimal outlier removal in high-dimensional
by: John Dunagan, Santosh Vempala
Interaction in quantum communication and the complexity of set disjointness
by: Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman
Regular resolution lower bounds for the weak pigeonhole principle
by: Toniann Pitassi, Ran Raz
The price of selfish routing
by: Marios Mavronicolas, Paul G. Spirakis
Colouring graphs when the number of colours is nearly the maximum degree
by: Michael Molloy, Bruce A. Reed
Explicit lower bound of 4.5n - o(n) for boolena circuits
by: Oded Lachish, Ran Raz
Data-streams and histograms
by: Sudipto Guha, Nick Koudas, Kyuseok Shim
A constant factor approximation for the single sink edge installation problems
by: Sudipto Guha, Adam Meyerson, Kamesh Munagala
Algorithms for minimizing weighted flow time
by: Chandra Chekuri, Sanjeev Khanna, An Zhu
Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
by: Daniel A. Spielman, Shang-Hua Teng
Non-approximability results for optimization problems on bounded degree instances
by: Luca Trevisan
Spatial gossip and resource location protocols
by: David Kempe, Jon M. Kleinberg, Alan J. Demers
Loss-less condensers, unbalanced expanders, and extractors
by: Amnon Ta-Shma, Christopher Umans, David Zuckerman
Sampling algorithms: lower bounds and applications
by: Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar
Fully-dynamic min-cut
by: Mikkel Thorup
On the integrality ratio of semidefinite relaxations of MAX CUT
by: Uriel Feige, Gideon Schechtman
Online server allocation in a server farm via benefit task systems
by: T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko
Clustering to minimize the sum of cluster diameters
by: Moses Charikar, Rina Panigrahy
Approximating min-sum k-clustering in metric spaces
by: Yair Bartal, Moses Charikar, Danny Raz
A sieve algorithm for the shortest lattice vector problem
by: Miklós Ajtai, Ravi Kumar, D. Sivakumar
Concurrent and resettable zero-knowledge in poly-loalgorithm rounds
by: Joe Kilian, Erez Petrank
Conditions on input vectors for consensus solvability in asynchronous distributed systems
by: Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal
Quantum mechanical algorithms for the nonabelian hidden subgroup problem
by: Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani
Computing with continuous-time Liapunov systems
by: Jirí Síma, Pekka Orponen
Spectral analysis of data
by: Yossi Azar, Amos Fiat, Anna R. Karlin, Frank McSherry, Jared Saia
Biased dictionaries with fast insert/deletes
by: Funda Ergün, Süleyman Cenk Sahinalp, Jonathan Sharp, Rakesh K. Sinha
Testing metric properties
by: Michal Parnas, Dana Ron
Extractor codes
by: Amnon Ta-Shma, David Zuckerman
Private approximation of NP-hard functions
by: Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim
A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D
by: Christian Icking, Lihong Ma
Quantitative solution of omega-regular games
by: 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 dimension
by: Bernard Chazelle, Ding Liu
Approximate distance oracles
by: Mikkel Thorup, Uri Zwick
Running time and program size for self-assembled squares
by: Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang
The complexity of maximal constraint languages
by: Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons
Euler paths in series parallel graphs
by: S. Rao Kosaraju
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
by: Mark Jerrum, Alistair Sinclair, Eric Vigoda
Profit-earning facility location
by: Adam Meyerson
On optimal slicing of parallel programs
by: Markus Müller-Olm, Helmut Seidl
A new protocol and lower bounds for quantum coin flipping
by: Andris Ambainis
Communication preserving protocols for secure function evaluation
by: Moni Naor, Kobbi Nissim
Anti-presistence: history independent data structures
by: Moni Naor, Vanessa Teague
Approximation algorithms for constrained for constrained node weighted steiner tree problems
by: Anna Moss, Yuval Rabani
Randomness efficient identity testing of multivariate polynomials
by: Adam Klivans, Daniel A. Spielman
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
by: Michel X. Goemans, David P. Williamson
A sharp threshold in proof complexity
by: Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy
Complex tilings
by: Bruno Durand, Leonid A. Levin, Alexander Shen
Excellent codes from modular curves
by: Noam D. Elkies
Sharp threshold and scaling window for the integer partitioning problem
by: Christian Borgs, Jennifer T. Chayes, Boris Pittel
(1+epsilon, beta)-spanner constructions for general graphs
by: Michael Elkin, David Peleg
Learning mixtures of arbitrary gaussians
by: Sanjeev Arora, Ravi Kannan
Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines
by: Luca Becchetti, Stefano Leonardi
Distribution functions of probabilistic automata
by: Farrokh Vatan
Provisioning a virtual private network: a network design problem for multicommodity flow
by: Anupam Gupta, Jon M. Kleinberg, Amit Kumar, Rajeev Rastogi, Bülent Yener
Fast computation of low rank matrix
by: Dimitris Achlioptas, Frank McSherry
Quantum algorithms for solvable groups
by: John Watrous

2000

Isomorphism testing for embeddable graphs through definability
by: Martin Grohe
On the approximability of the traveling salesman problem (extended abstract)
by: Christos H. Papadimitriou, Santosh Vempala
Higher lower bounds on monotone size
by: Danny Harnik, Ran Raz
Rapid sampling though quantum computing
by: Lov K. Grover
More general completeness theorems for secure two-party computation
by: 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 graphs
by: 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 representations
by: Sean Hallgren, Alexander Russell, Amnon Ta-Shma
A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees
by: Jochen Könemann, R. Ravi
Near optimal multiple alignment within a band in polynomial time
by: Ming Li, Bin Ma, Lusheng Wang
Matrix-vector product for confluent Cauchy-like matrices with application to confluent rational interpolation
by: Vadim Olshevsky, Mohammad Amin Shokrollahi
From partial consistency to global broadcast
by: 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 operations
by: 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 model
by: Avrim Blum, Adam Kalai, Hal Wasserman
Finding smooth integers in short intervals using CRT decoding
by: 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 drawings
by: Guy Even, Sudipto Guha, Baruch Schieber
Shortest path queries in planar graphs
by: 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 algorithms
by: 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 computation
by: Ronald Cramer, Ivan Damgård, Stefan Dziembowski
A unified approach to approximating resource allocation and scheduling
by: 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 matrices
by: Steven Fortune
The value of strong inapproximability results for clique
by: Aravind Srinivasan
Compression using efficient multicasting
by: 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 protocols
by: Hartmut Klauck
List decoding algorithms for certain concatenated codes
by: Venkatesan Guruswami, Madhu Sudan
On the efficiency of local decoding procedures for error-correcting codes
by: Jonathan Katz, Luca Trevisan
Complete characterization of security notions for probabilistic private-key encryption
by: Jonathan Katz, Moti Yung
Faster suffix tree construction with missing suffix links
by: Richard Cole, Ramesh Hariharan
More theory revision with queries (extended abstract)
by: Judy Goldsmith, Robert H. Sloan
Connectivity and inference problems for temporal networks
by: David Kempe, Jon M. Kleinberg, Amit Kumar
A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
by: Satoru Iwata, Lisa Fleischer, Satoru Fujishige
Near-optimal fully-dynamic graph connectivity
by: Mikkel Thorup
Combining fairness with throughput: online routing with multiple objectives
by: Ashish Goel, Adam Meyerson, Serge A. Plotkin
On transformation of interactive proofs that preserve the prover's complexity
by: Salil P. Vadhan
Polynomial-time approximation scheme for data broadcast
by: Claire Kenyon, Nicolas Schabanel, Neal E. Young
Balanced allocations: the heavily loaded case
by: Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vöcking
A constant factor approximation algorithm for a class of classification problems
by: 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 packing
by: 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 complexity
by: Alex Samorodnitsky, Luca Trevisan
Tighter bounds for nearest neighbor search and related problems in the cell probe model
by: Omer Barkol, Yuval Rabani
Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
by: 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 escrow
by: 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