Explicit capacity-achieving list-decodable codes.
Gowers uniformity, influence of variables, and PCPs.
Sub-constant error low degree test of almost-linear size.
The Santa Claus problem.
On maximizing welfare when utility functions are subadditive.
A randomized polynomial-time simplex algorithm for linear programming.
Reducibility among equilibrium problems.
The complexity of computing a Nash equilibrium.
New trade-offs in cost-sharing mechanisms.
The effect of collusion in congestion games.
Black-box constructions for secure computation.
Information-theoretically secure protocols and security under composition.
Private approximation of search problems.
The changing face of web search: algorithms, auctions and advertising.
On the solution-space geometry of random constraint satisfaction problems.
Counting independent sets up to the tree threshold.
The DLT priority sampling is essentially optimal.
Optimal phylogenetic reconstruction.
Time-space tradeoffs for implementations of snapshots.
Byzantine agreement in the full-information model in O(log n) rounds.
Fast leader-election protocols with bounded cheaters' edge.
Pricing for fairness: distributed resource allocation for multiple objectives.
Near-optimal algorithms for unique games.
New approximation guarantee for chromatic number.
Finding a maximum weight triangle in n<sup>3-Delta</sup> time, with applications.
Time-space trade-offs for predecessor search.
The PCP theorem by gap amplification.
A combinatorial characterization of the testable graph properties: it's all about regularity.
Graph limits and parameter testing.
Advances in metric embedding theory.
Zero knowledge with efficient provers.
Zero-knowledge against quantum attacks.
Local zero knowledge.
A quasi-polynomial time approximation scheme for minimum weight triangulation.
Building triangulations using epsilon-nets.
The distance trisector curve.
Conditional hardness for approximate coloring.
Clique-width minimization is NP-hard.
Hardness of approximate two-level logic minimization and PAC learning with membership queries.
Can every randomized algorithm be derandomized?
Finding small balanced separators.
Graph partitioning using single commodity flows.
Linear time low tree-width partitions and algorithmic consequences.
Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs.
Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications.
A polynomial quantum algorithm for approximating the Jones polynomial.
On the fourier tails of bounded functions over the discrete cube.
Lattice problems and norm embeddings.
Pseudorandom walks on regular digraphs and the RL vs. L problem.
An efficient algorithm for solving word equations.
Online trading algorithms and robust option pricing.
On adequate performance measures for paging.
Extractors for a constant number of polynomially small min-entropy independent sources.
Narrow proofs may be spacious: separating space and width in resolution.
Logarithmic hardness of the directed congestion minimization problem.
Hardness of cut problems in directed graphs.
Integrality gaps for sparsest cut and minimum linear arrangement problems.
On earthmover distance, metric labeling, and 0-extension.
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform.
On the importance of idempotence.
Searching dynamic point sets in spaces with bounded doubling dimension.
Learning a circuit by injecting values.
Bounded-error quantum state identification and exponential separations in communication complexity.
Limitations of quantum coset states for graph isomorphism.
A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs.
New upper and lower bounds for randomized and quantum local search.
Truthful randomized mechanisms for combinatorial auctions.
Fast convergence to Wardrop equilibria by adaptive sampling methods.
Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree.
2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction.
Linear degree extractors and the inapproximability of max clique and chromatic number.
Deterministic extractors for small-space sources.
On basing one-way functions on NP-hardness.
On the randomness complexity of efficient sampling.
A quasi-PTAS for unsplittable flow on line graphs.
Minimizing average flow time on related machines.
Provably near-optimal sampling-based algorithms for Stochastic inventory control models.
A subset spanner for Planar graphs, : with application to subset TSP.
Edge-disjoint paths in Planar graphs with constant congestion.
Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors.
Extractors with weak random seeds.
Pseudorandom generators for low degree polynomials.
On uniform amplification of hardness in NP.
Approximation techniques for utilitarian mechanism design.
Computing correlated equilibria in multi-player games.
Large the price of routing unsplittable flow.
The price of anarchy of finite congestion games.
Market equilibrium via the excess demand function.
On lattices, learning with errors, random linear codes, and cryptography.
Representing hard lattices with O(n log n) bits.
On dynamic range reporting in one dimension.
Worst-case update times for fully-dynamic all-pairs shortest paths.
Beyond NP: the work and legacy of Larry Stockmeyer.
Every monotone graph property is testable.
Testing versus estimation of graph properties.
Testing monotone high-dimensional distributions.
Efficient testing of groups.
Approximation algorithms for network design with metric costs.
On non-uniform multicommodity buy-at-bulk network design.
Multicommodity flow, well-linked terminals, and routing problems.
Oblivious routing in directed graphs with random demands.
Optimal approximations of the frequency moments of data streams.
Coresets in dynamic geometric data streams.
Low distortion embeddings for edit distance.
Low-distortion embeddings of general metrics into the line.
Tree-walking automata do not recognize all regular languages.
Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read.
Lower bounds for k-DNF resolution on random 3-CNFs.
Bounded-depth circuits: separating wires from gates.
Simple PCPs with poly-log rate and query complexity.
Hardness of the undirected edge-disjoint paths problem.
Hardness of the undirected congestion minimization problem.
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy.
Computing the first Betti number and the connected components of semi-algebraic sets.
Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities.
On algorithms for discrete and approximate brouwer fixed points.
Convex programming for scheduling unrelated parallel machines.
The round complexity of two-party random selection.
Hierarchies for semantic classes.
Learning with attribute costs.
Learning nonsingular phylogenies and hidden Markov models.
Undirected ST-connectivity in log-space.
Universal approximations for TSP, Steiner tree, and set cover.
Saving an epsilon: a 2-approximation for the k-MST problem in graphs.
The mixing time of the Thorp shuffle.
Approximately counting integral flows and cell-bounded contingency tables.
Spectral norm of random matrices.
On random pm 1 matrices: singularity and determinant.
On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem.
Towards asymptotic optimality in probabilistic packet marking.
Tensor norms and the classical communication complexity of nonlocal quantum measurement.
Fast quantum algorithms for computing the unit group and class group of a number field.
Polynomial time quantum algorithm for the computation of the unit group of a number field.
Fast quantum byzantine agreement.
Quadratic forms on graphs.
Lower-stretch spanning trees.
Edge partition of planar sraphs into two outerplanar graphs.
Covert two-party computation.
On obfuscating point functions.
New and improved constructions of non-malleable cryptographic protocols.
Collusion-free protocols.
Euclidean distortion and the sparsest cut.
Improved approximation algorithms for minimum-weight vertex separators.
O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems.
Balanced metric labeling.
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits.
Limits to list decoding Reed-Solomon codes.
Approximation algorithms for combinatorial auctions with complement-free bidders.
Derandomization of auctions.
An O(log n log log n) space algorithm for undirected st-connectivity.
The complexity of agreement.
Concurrent general composition of secure protocols in the timing model.
Correcting errors without leaking partial information.
Key agreement from weak bit agreement.
A new strategy for querying priced information.
Aggregating inconsistent information: ranking and clustering.
On the bias of traceroute sampling: or, power-law degree distributions in regular graphs.
How to spread adversarial nodes?: rotate!
From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement.
An optimal multi-writer snapshot algorithm.
Cooperative asynchronous update of shared memory.
Every 2-CSP allows nontrivial approximation.
Tensor decomposition and approximation schemes for constraint satisfaction problems.
On strip packing With rotations.
Robust pcps of proximity, shorter pcps and applications to coding.
A new PCP outer verifier with applications to homogeneous linear equations and max-bisection.
Asymmetric k-center is log<sup>*</sup> <i>n</i>-hard to approximate.
New hardness results for congestion minimization and machine scheduling.
On the performance of greedy algorithms in packet buffering.
Adaptive routing with end-to-end feedback: distributed learning and geometric approaches.
Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks.
The zero-one principle for switching networks.
Approximating the cut-norm via Grothendieck's inequality.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.
Dictionary matching and indexing with errors and don't cares.
Sorting and searching in the presence of memory faults (without redundancy).
Quantum algorithms a decade after shor.
Graph entropy and quantum sorting problems.
Multilinear formulas and skepticism of quantum computing.
Exponential separation of quantum and classical one-way communication complexity.
Approximation algorithm for k-node connected subgraphs via critical graphs.
Solving fractional packing problems in <i>O</i><sup>ast</sup>(1/?) iterations.
The all-or-nothing multicommodity flow problem.
Approximation algorithms for deadline-TSP and vehicle routing with time-windows.
Estimating the weight of metric minimum spanning trees in sublinear-time.
A fully dynamic reachability algorithm for directed graphs with an almost linear update time.
Using nondeterminism to amplify hardness.
Visibly pushdown languages.
Linear FPT reductions and computational lower bounds.
Expander flows, geometric embeddings and graph partitioning.
Bounded-concurrent secure multi-party computation with a dishonest majority.
New notions of security: achieving universal composability without trusted setup.
Completeness in two-party secure computation: a computational view.
Batch codes and their applications.
Low distortion maps between point sets.
Bypassing the embedding: algorithms for low dimensional metrics.
On coresets for k-means and k-median clustering.
Isotopic implicit surface meshing.
Hit-and-run from a corner.
A simple polynomial-time rescaling algorithm for solving linear programs.
Collective asynchronous reading with polylogarithmic worst-case overhead.
Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem.
Network games.
Typical properties of winners and losers in discrete optimization.
Primal-dual algorithms for deterministic inventory problems.
Multi-processor scheduling to minimize flow time with epsilon resource augmentation.
Algorithms for dynamic geometric problems over data streams.
Sublinear algorithms for testing monotone and unimodal distributions.
The difficulty of testing for isomorphism against a graph that is given in advance.
An approximate K&ouml;nig's theorem for edge-coloring weighted bipartite graphs.
Finding paths and cycles of superpolylogarithmic length.
Boosted sampling: approximation algorithms for stochastic optimization.
Derandomizing homomorphism testing in general groups.
Better extractors for better codes?
A new family of Cayley expanders (?).
Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus.
Lower bounds for local search by quantum arguments.
Counting complexity classes for numeric computations II: algebraic and semialgebraic sets.
A conjecture about polynomial time computable lattice-lattice functions.
Quantum and classical query complexities of local search are polynomially related.
The quantum adiabatic optimization algorithm and local minima.
Auction algorithms for market equilibrium.
The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results.
(Almost) tight bounds and existence theorems for confluent flows.
Approximate max-integral-flow/min-multicut theorems.
Lower bounds for dynamic connectivity.
Lower bounds for linear degeneracy testing.
A decentralized algorithm for spectral analysis.
Using mixture models for collaborative filtering.
Depth through breadth, or why should we attend talks in other areas?
Sharp thresholds For monotone properties in random geometric graphs.
The two possible values of the chromatic number of a random graph.
On sums of independent random variables with unbounded variance, and estimating the average degree in a graph.
The complexity of pure Nash equilibria.
Computing Nash equilibria for scheduling on restricted parallel links.
Rational secret sharing and multiparty computation: extended abstract.
Multi-linear formulas for permanent and determinant are of super-polynomial size.
Hidden translation and orbit coset in quantum computing.
Classical deterministic complexity of Edmonds' Problem and quantum entanglement.
Adiabatic quantum state generation and statistical zero knowledge.
Better streaming algorithms for clustering problems.
Approximation algorithms for hierarchical location problems.
Approximation schemes for clustering problems.
Exponential algorithmic speedup by a quantum walk.
Quantum time-space tradeoffs for sorting.
On the power of quantum fingerprinting.
Management of multi-queue switches in QoS networks.
Constant factor approximation of vertex-cuts in planar graphs.
The online set cover problem.
Exponential lower bound for 2-query locally decodable codes via a quantum argument.
Optimal probabilistic fingerprint codes.
Linear time encodable and list decodable codes.
Reconstructing curves in three (and higher) dimensional space from noisy data.
Short path queries in planar graphs in constant time.
Integer priority queues with decrease key in constant time and the single source shortest paths problem.
A new approach to dynamic all pairs shortest paths.
A fast algorithm for computing steiner edge connectivity.
The computational complexity of some julia sets.
Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions.
Boosting in the presence of noise.
Learning juntas.
Generating random regular graphs.
The threshold for random k-SAT is 2<sup>k</sup> (ln 2 - O(k)).
Random knapsack in expected polynomial time.
Server scheduling in the L<sub>p</sub> norm: a rising tide lifts all boat.
Work-competitive scheduling for cooperative computing with dynamic groups.
A tight time lower bound for space-optimal implementations of multi-writer snapshots.
Randomly coloring graphs of girth at least five.
Evolving sets and mixin.
Modified log-sobolev inequalities, mixing and hypercontractivity.
On the fractal behavior of TCP.
On the limits of cache-obliviousness.
A sublinear algorithm for weakly approximating edit distance.
New degree bounds for polynomial threshold functions.
Sampling lower bounds via information theory.
Some 3CNF properties are hard to test.
Derandomizing polynomial identity tests means proving circuit lower bounds.
Simpler and better approximation algorithms for network design.
Meet and merge: approximation algorithms for confluent flows.
Optimal oblivious routing in polynomial time.
Primal-dual meets local search: approximating MST's with nonuniform degree bounds.
The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice.
New lattice based cryptographic constructions.
Lower bounds on the efficiency of encryption and digital signature schemes.
Non-interactive and reusable non-malleable commitment schemes.
The intrinsic dimensionality of graphs.
A tight bound on approximating arbitrary metrics by tree metrics.
On average distortion of embedding metrics into the line and into L1.
On metric ramsey-type phenomena.
Touring a sequence of polygons.
Well-separated pair decomposition for the unit-disk graph metric and its applications.
Alpha-shapes and flow shapes are homotopy equivalent.
Reducing truth-telling online mechanisms to online optimization.
Near-optimal network design with selfish agents.
Pricing network edges for heterogeneous selfish users.
Sublinear geometric algorithms.
Distinct distances in three and higher dimensions.
Cutting triangular cycles of lines in space.
OPT versus LOAD in dynamic storage allocation.
Consistent load balancing via spread minimization.
A stochastic process on the hypercube with applications to peer-to-peer networks.
Polylogarithmic inapproximability.
A new multilayered PCP and the hardness of hypergraph vertex cover.
Extractors: optimal up to constant factors.
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets.
Uniform hashing in constant time and linear space.
Almost random graphs with simple hash functions.
Dynamic rectangular intersection with priorities.
Space efficient dynamic stabbing with fast queries.
Lower bounds on the amount of randomness in private computation.
Cell-probe lower bounds for the partial match problem.
Two applications of information complexity.
Bounded-concurrent secure two-party computation without setup assumptions.
Approximate counting by dynamic programming.
Testing subgraphs in directed graphs.
On the sample size of k-restricted min-wise independent permutations and other k-wise distributions.
A proof of Alon's second eigenvalue conjecture.
Recognizing string graphs in NP.
Dynamic subgraph connectivity with geometric applications.
New results on monotone dualization and generating hypergraph transversals.
Combinatorial optimization problems in self-assembly.
The importance of being biased.
On the advantage over a random assignment.
The complexity of choosing an H-colouring (nearly) uniformly at random.
Random sampling in residual graphs.
On the complexity of equilibria.
Competitive generalized auctions.
Competitive recommendation systems.
The Glauber dynamics on colourings of a graph with high girth and maximum degree.
Clairvoyant scheduling of random walks.
Solving convex programs by random walks.
The Joy of Theory.
Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths.
Lower bounds &amp; competitive algorithms for online scheduling of unit-size tasks to related machines.
On randomized online scheduling.
On the complexity of matrix product.
Near-optimal sparse fourier representations via sampling.
Fitting algebraic curves to noisy data.
A new average case analysis for completion time scheduling.
A unified analysis of hot video schedulers.
Optimal rate-based scheduling on multiprocessors.
Almost all graphs with average degree 4 are 3-colorable.
Models and thresholds for random constraint satisfaction problems.
Reimer's inequality and tardos' conjecture.
Clifford algebras and approximating the permanent.
Random sampling and approximation of MAX-CSP problems.
A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant.
Approximate clustering via core-sets.
On paging with locality of reference.
Cache-oblivious priority queue and graph algorithm applications.
Average case analysis for batched disk scheduling and increasing subsequences.
Selfish traffic allocation for server farms.
Approximation schemes for preemptive weighted flow time.
Approximation algorithms for minimum-cost k-vertex connected subgraphs.
Equitable cost allocations via primal-dual-type algorithms.
2-round zero knowledge and proof auditors.
Concurrent zero-knowledge with timing, revisited.
Tight security proofs for the bounded-storage model.
Hardness results for approximate hypergraph coloring.
Space lower bounds for distance approximation in the data stream model.
Approximate counting of inversions in a data stream.
Similarity estimation techniques from rounding algorithms.
Fast, small-space algorithms for approximate histogram maintenance.
Stability of load balancing algorithms in dynamic adversarial systems.
Tradeoffs in probabilistic packet marking for IP traceback.
Crawling on web graphs.
The price of anarchy is independent of the network topology.
Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem.
An exponential separation between regular and general resolution.
Size space tradeoffs for resolution.
Exact learning of DNF formulas using DNF hypotheses.
Monotonicity testing over general poset domains.
Strict polynomial-time in simulation and extraction.
Universally composable two-party and multi-party secure computation.
The invasiveness of off-line memory checking.
On the composition of authenticated byzantine agreement.
Wait-free consensus with infinite arrivals.
Relations between average case complexity and approximation complexity.
Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilon.
Resolution lower bounds for the weak pigeonhole principle.
Hard examples for bounded depth frege.
Meldable heaps and boolean union-find.
Optimal finger search trees in the pointer machine.
Verifying candidate matches in sparse and wildcard matching.
Deterministic sorting in O(nlog log n) time and linear space.
Improved cryptographic hash functions with worst-case/average-case connection.
Algorithmic derandomization via complexity theory.
Pseudo-random generators for all hardnesses.
Quantum lower bound for the collision problem.
Secure multi-party quantum computation.
Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem.
Randomness conductors and constant-degree lossless expanders.
Expanders from symmetric codes.
The complexity of approximating entropy.
Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems.
On communication over an entanglement-assisted quantum channel.
Girth and euclidean distortion.
Computing the betti numbers of arrangements.
Space-efficient approximate Voronoi diagrams.
A new greedy approach for facility location problems.
Finding nearest neighbors in growth-restricted metrics.
Hardness amplification within NP.
3-manifold knot genus is NP-complet.
On the power of unique 2-prover 1-round games.
Learnability beyond AC0.
Huffman coding with unequal letter costs.
Approximating the smallest grammar: Kolmogorov complexity in natural models.
Limits to list decodability of linear codes.
Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets.
Clustering to minimize the sum of cluster diameters.
Approximating min-sum <i>k</i>-clustering in metric spaces.
Local search heuristic for k-median and facility location problems.
Profit-earning facility location.
One-dimensional quantum walks.
Quantum walks on graphs.
Quantum algorithms for solvable groups.
Quantum mechanical algorithms for the nonabelian hidden subgroup problem.
Minimax parametric optimization problems and multi-dimensional parametric searching.
Algorithms for minimizing weighted flow time.
Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines.
Stackelberg scheduling strategies.
Quantum computers that can be simulated classically in polynomial time.
Interaction in quantum communication and the complexity of set disjointness.
A new protocol and lower bounds for quantum coin flipping.
Loss-less condensers, unbalanced expanders, and extractors.
Conditions on input vectors for consensus solvability in asynchronous distributed systems.
Spatial gossip and resource location protocols.
(1+epsilon, beta)-spanner constructions for general graphs.
Approximate distance oracles.
Extractor codes.
Excellent codes from modular curves.
Sparse polynomial approximation in finite fields.
Randomness efficient identity testing of multivariate polynomials.
Fully-dynamic min-cut.
Computing crossing numbers in quadratic time.
Euler paths in series parallel graphs.
Decidability of string graphs.
Learning mixtures of arbitrary gaussians.
Learning DNF in time 2<sup>&Otilde;(n<sup>1/3</sup>)</sup>.
Sampling algorithms: lower bounds and applications.
Testing metric properties.
Testing of matrix properties.
Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time.
One line and n points.
A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D.
Lower bounds for intersection searching and fractional cascading in higher dimension.
Sharp threshold and scaling window for the integer partitioning problem.
A sharp threshold in proof complexity.
Regular resolution lower bounds for the weak pigeonhole principle.
The complexity of analytic tableaux.
Applications of approximation algorithms to cooperative games.
Approximation algorithms for constrained for constrained node weighted steiner tree problems.
A constant factor approximation for the single sink edge installation problems.
Provisioning a virtual private network: a network design problem for multicommodity flow.
Explicit lower bound of <i>4.5n - o(n)</i> for boolena circuits.
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates.
A read-once branching program lower bound of Omega(2<sup>n/4</sup>) for integer multiplication using universal.
On the cell probe complexity of membership and perfect hashing.
On the integrality ratio of semidefinite relaxations of MAX CUT.
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming.
Non-approximability results for optimization problems on bounded degree instances.
Colouring graphs when the number of colours is nearly the maximum degree.
Data-streams and histograms.
Optimal static range reporting in one dimension.
Biased dictionaries with fast insert/deletes.
Anti-presistence: history independent data structures.
Dynamic TCP acknowledgement and other stories about e/(e-1).
The price of selfish routing.
Buffer overflow management in QoS switches.
Almost optimal permutation routing on hypercubes.
Online server allocation in a server farm via benefit task systems.
Private approximation of NP-hard functions.
Concurrent and resettable zero-knowledge in poly-loalgorithm rounds.
Black-box concurrent zero-knowledge requires Omega~(log n) rounds.
The round complexity of verifiable secret sharing and secure multicast.
Communication preserving protocols for secure function evaluation.
Some perspective on computational complexity (abstract).
A sieve algorithm for the shortest lattice vector problem.
Fast computation of low rank matrix.
Spectral analysis of data.
Optimal outlier removal in high-dimensional.
Estimating true evolutionary distances between genomes.
On optimal slicing of parallel programs.
When is the evaluation of conjunctive queries tractable?
The complexity of maximal constraint languages.
Quantitative solution of omega-regular games.
Distribution functions of probabilistic automata.
Compatible sequences and a slow Winkler percolation.
Edge isoperimetry and rapid mixing on matroids and geometric Markov chains.
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries.
Computing with continuous-time Liapunov systems.
Complex tilings.
Running time and program size for self-assembled squares.
Algorithms, games, and the internet.
Automata, circuits and hybrids: facets of continuous time.
Extractors and pseudo-random generators with optimal seed length.
Pseudo-random functions and factoring (extended abstract).
Satisfiability of equations in free groups is in PSPACE.
Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract).
A new algorithm approach to the general Lov&aacute;sz local lemma with applications to scheduling and satisfiability problems (extended abstract).
A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume.
Randomized metarounding (extended abstract).
Isomorphism testing for embeddable graphs through definability.
Circuit minimization problem.
On the efficiency of local decoding procedures for error-correcting codes.
Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intracatability for the partition function of the Ising model across non-planar surfaces (extended abstract).
A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions.
Improved algorithms for submodular function minimization and submodular flow.
On dual minimum cost flow algorithms (extended abstract).
On the approximability of the traveling salesman problem (extended abstract).
Approximating the domatic number.
The value of strong inapproximability results for clique.
Compression using efficient multicasting.
The small-world phenomenon: an algorithm perspective.
A random graph model for massive graphs.
List decoding algorithms for certain concatenated codes.
A PCP characterization of NP with optimal amortized query complexity.
On transformation of interactive proofs that preserve the prover's complexity.
On the sum-of-squares algorithm for bin packing.
Sharing the cost of muliticast transmissions (preliminary version).
The risk profile problem for stock portfolio optimization (extended abstract).
Resettable zero-knowledge (extended abstract).
Complete characterization of security notions for probabilistic private-key encryption.
On zero-knowledge proofs (extended abstract): ``from membership to decision''.
Finding smooth integers in short intervals using CRT decoding.
Smoothing and cleaning up slivers.
Hard-Potato routing.
Approximation algorithms for geometric shortest path problems.
Improved approximations of crossings in graph drawings.
On the decidability of accessibility problems (extended abstract).
More general completeness theorems for secure two-party computation.
On the complexity of verifiable secret sharing and multiparty computation.
Tight(er) worst-case bounds on dynamic searching and priority queues.
Near-optimal fully-dynamic graph connectivity.
A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract).
Space complexity in propositional calculus.
A new proof of the weak pigeonhole principle.
Higher lower bounds on monotone size.
Tighter bounds for nearest neighbor search and related problems in the cell probe model.
Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract).
Faster suffix tree construction with missing suffix links.
Approximate nearest neighbors and sequence comparison with block operations.
Near optimal multiple alignment within a band in polynomial time.
Noise-tolerant learning, the parity problem, and the statistical query model.
More theory revision with queries (extended abstract).
Are bitvectors optimal?
The program-size complexity of self-assembled squares (extended abstract).
Shortest path queries in planar graphs.
How tall is a tree?
Random walks with ``back buttons'' (extended abstract).
From partial consistency to global broadcast.
Connectivity and inference problems for temporal networks.
Strictly non-blocking WDM cross-connects for heterogeneous networks.
Finding long paths and cycles in sparse Hamiltonian graphs.
Approximating the minimum bisection size (extended abstract).
A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees.
Clustering for edge-cost minimization (extended abstract).
Exact computations of the inertia symmetric integer matrices.
epsilon-optimization schemes and L-bit precision: alternative perspectives in combinatorial optimization (extended abstract).
Matrix-vector product for confluent Cauchy-like matrices with application to confluent rational interpolation.
Query strategies for priced information (extended abstract).
A guessing game and randomized online algorithms.
Computing the median with uncertainty.
Parallelization, amplification, and exponential time simulation of quantum interactive proof systems.
Rapid sampling though quantum computing.
Normal subgroup reconstruction and quantum computation using group representations.
Quantum lower bounds by quantum arguments.
On quantum and probabilistic communication: Las Vegas and one-way protocols.
A constant factor approximation algorithm for a class of classification problems.
Polynomial-time approximation scheme for data broadcast.
Approximating permanents of complex matrices.
Combining fairness with throughput: online routing with multiple objectives.
Improvements in throughout maximization for real-time scheduling.
Self-testing of universal and fault-tolerant sets of quantum gates.
Computing with highly mixed states (extended abstract).
Quantum bit escrow.
A proof of the security of quantum key distribution (extended abstract).
Better algorithms for unfair metrical task systems and applications.
A unified approach to approximating resource allocation and scheduling.
Balanced allocations: the heavily loaded case.
A Constant-Factor Approximation Algorithm for the <i>k</i>-Median Problem (Extended Abstract).
A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow.
Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems.
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.
Fast Approximate PCPs.
Approximate Testing with Relative Error.
All Pairs Lightest Shortest Paths.
Unique Maximum Matching Algorithms.
Improved Upper Bounds on Information-Theoretic Private Information Retrieval (Extended Abstract).
One-Way Functions Are Essential for Single-Server Private Information Retrieval.
On targeting Markov segments.
Exploiting Regularities in Web Traffic Patterns for Cache Replacement.
Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily Returns.
Algorithmic Mechanism Design (Extended Abstract).
Construction of Extractors Using Pseudo-Random Generators (Extended Abstract).
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.
On Recycling the Randomness of States in Space Bounded Computation.
Security-Preserving Hardness-Amplification for Any Regular One-Way Function.
Scheduling in the Dark.
Scheduling Data Transfers in a Network and the Set Scheduling Problem.
Minimizing the Flow Time Without Migration.
Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks.
From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols.
Chinese Remaindering with Errors.
A Displacement Approach to Efficient Decoding of Algebraic-Geometric Codes.
Oblivious Transfer and Polynomial Evaluation.
Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? (Extended Abstract).
Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (Extended Abstract).
Lifting Markov Chains to Speed up Mixing.
Faster Mixing via Average Conductance.
Majorizing Estimators and the Approximation of #P-Complete Problems.
Optimal Bounds for the Predecessor Problem.
A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube.
Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems.
Molecular Scale Heat Engines and Scalable Quantum Computation.
Quantum Fourier Sampling Simplified.
Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model.
A Theorem on Sensitivity and Applications in Private Computation.
Exponential Separation of Quantum and Classical Communication Complexity.
Undecidability on Quantum Finite Automata.
Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata.
The Quantum Query Complexity of Approximating the Median and Related Statistics.
Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme.
A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines.
Improved Approximation Schemes for Scheduling Unrelated Parallel Machines.
A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (Extended Abstract).
Sublinear Time Algorithms for Metric Space Problems.
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces.
Covering Rectilinear Polygons with Axis-Parallel Rectangles.
Compact Grid Layouts of Multi-Level Networks.
Complexity of Graph Partition Problems.
Finding Similar Regions in Many Strings.
Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems.
A Fully Dynamic Algorithm for Maintaining the Transitive Closure.
Worst-Case and Amortised Optimality in Union-Find (Extended Abstract).
The Complexity of the Matrix Eigenproblem.
Short Proofs are Narrow - Resolution Made Simple.
On the Complexity of Diophantine Geometry in Low Dimensions (Extended Abstract).
Pseudorandom Generators Without the XOR Lemma (Extended Abstract).
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes.
Packet Routing with Arbitrary End-to-End Delay Requirements.
Static and Dynamic Evaluation of QoS Properties.
Efficient Recovery from Power Outage (Extended Abstract).
Nonmonotonic Phenomena in Packet Routing.
Graph Ramsey Theory and the Polynomial Hierarchy.
The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling.
Connection Caching.
Approximating the Throughput of Multiple Machines Under Real-Time Scheduling.
Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract).
Robust Logics.
Hypergraph Isomorphism and Structural Equivalence of Boolean Functions.
Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut.
Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems.
Approximation Schemes for Minimum Latency Problems.
Embedding Tree Metrics Into Low Dimensional Euclidean Spaces.
Computational Sample Complexity and Attribute-Efficient Learning.
On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice.
Satisfiability of Word Equations with Constants is in NEXPTIME.
Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time.
Inerpolation of Symmetric Functions and a New Type of Combinatorial Design.
Small Universal Graphs.
Design Networks with Bounded Pairwise Distance.
Random Sampling of Large Planar Maps and Convex Polyhedra.
Efficient Computation of Geodesic Shortest Paths.
Backing Up in Singly Linked Lists.
On the Limits of Non-Approximability of Lattice Problems.
The Shortest Vector Problem in <i>L<sub>2</sub></i> is <i>NP</i>-hard for Randomized Reductions (Extended Abstract).
Quantum Circuits with Mixed States.
Exact Sampling and Approximate Counting Techniques.
A Polynomial Approximation Algorithm for the Minimum Fill-In Problem.
An Improved Approximation Algorithm for Multiway Cut.
A Framework for Fast Quantum Mechanical Algorithms.
Quantum vs. Classical Communication and Computation.
Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching.
Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity.
Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract).
Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems.
Approximation Schemes for Euclidean <i>k</i>-Medians and Related Problems.
Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and <i>k</i>-Median.
One Help Bit Doesn't Help.
Perfectly One-Way Probabilistic Hash Functions (Preliminary Version).
Non-Interactive and Non-Malleable Commitment.
Protecting Data Privacy in Private Information Retrieval Schemes.
On Approximating Arbitrary Metrices by Tree Metrics.
Trees and Euclidean Metrics.
Random Generation of Embedded Graphs and an Extension to Dobrushin Uniqueness (Extended Abstract).
Efficient Algorithms for Constructing Fault-Tolerant Geometric Spanners.
Almost Optimal Dispersers.
NP Might Not Be As Easy As Detecting Unique Solutions.
The Random Oracle Methodology, Revisited (Preliminary Version).
Randomized Complexity Lower Bounds.
Weak Alternating Automata and Tree Automata Emptiness.
Over Words, Two Variables Are as Powerful as One Quantifier Alternation.
Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound.
Analysis of Low Density Codes and Improved Designs Using Irregular Graphs.
Spot-Checkers.
The Power of a Pebble: Exploring and Mapping Directed Graphs.
Linear-Time Pointer-Machine Algorithms for Least Common Ancestors, MST Verification, and Dominators.
A Sublinear Bipartiteness Tester for Bunded Degree Graphs.
Recycling Queries in PCPs and in Linearity Tests (Extended Abstract).
The Closure of Monadic NP (Extended Abstract).
Information Theoretic Implications for Pairing Heaps.
Min-Wise Independent Permutations (Extended Abstract).
The Approximability of NP-hard Problems.
Algorithms for Capacitated Vehicle Routing.
Adaptive Packet Routing for Bursty Adversarial Traffic.
Stability Results for Networks with Input and Output Blocking.
Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks.
TCP Dynamic Acknowledgment Delay: Theory and Practice (Extended Abstract).
Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge.
Concurrent Zero-Knowledge.
A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols (Extended Abstract).
A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs.
Checking Polynomial Identities over any Field: Towards a Derandomization?
Multicasting in Heterogeneous Networks.
Minimizing Stall Time in Single and Parallel Disk Systems.
On Indexed Data Broadcast.
Segmentation Problems.
Computing Local Dimension of a Semialgebraic Set.
Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations.
A Black Box Approach to the Algebraic Set Decomposition Problem.
Are Lower Bounds Easier over the Reals?
Planar Map Graphs.
Further Algorithmic Aspects of the Local Lemma.
Decision Algorithms for Unsplittable Flow and the Half-Disjoint Paths Problem.
Approximating Geometrical Graphs via "Spanners" and "Banyans".
Finding Almost-Satisfying Assignments.
On the Complexity of Unsatisfiability Proofs for Random <i>k</i>-CNF Formulas.
<i>K</i>-sat on Groups and Undecidability.
An Exponential Lower Bound for Depth 3 Arithmetic Circuits.
A New Composition Theorem for Learning Algorithms.
Adaptive versus Nonadaptive Attribute-Efficient Learning.
On the Complexity of Protein Folding (Extended Abstract).
Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.
Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces.
Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract).
On Broadcast Disk Paging.
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents.
On Separating the Read-k-Times Branching Program Hierarchy.
Robust Efficient Distributed RSA-Key Generation.
The Cost of the Missing Bit: Communication Complexity with Help.
Some Optimal Inapproximability Results.
A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction.
When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract).
Approximate Complex Polynomial Evaluation in Near Constant Work Per Point.
Fast and Precise Computations of Discrete Fourier Transforms Using Cyclotomic Integers.
Quantum Computation of Fourier Transforms over Symmetric Groups.
General Techniques for Comparing Unrooted Evolutionary Trees.
Tree Pattern Matching and Subset Matching in Randomized O(n log<sup>3</sup>m) Time.
Randomized Omega(n<sup>2</sup>) Lower Bound for Knapsack.
Exponential Lower Bounds for Depth 3 Boolean Circuits.
Algorithmic Complexity in Coding Theory and the Minimum Distance Problem.
Approximating Total Flow Time on Parallel Machines.
Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics (Extended Abstract).
Better Bounds for Online Scheduling.
Optimal Time-Critical Scheduling via Resource Augmentation (Extended Abstract).
Practical Loss-Resilient Codes.
Spectral Techniques for Expander Codes.
Faster Solution of the Key Equation for Decoding BCH Error-Correcting Codes.
Fault-Tolerant Quantum Computation With Constant Error.
On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited (Extended Abstract).
Reducing Randomness via Irrational Numbers.
Is There an Algebraic Proof for <i>P != NC</i>? (Extended Abstract).
<i>P = BPP</i> if <i>E</i> Requires Exponential Circuits: Derandomizing the XOR Lemma.
SL &lt;= L<sup>4/3</sup>.
Using Random Sampling to Find Maximum Flows in Uncapacitated Undirected Graphs.
Combinatorial Complexity of the Central Curve.
Approximation of <i>k</i>-Set Cover by Semi-Local Optimization.
Approximation Algorithms for Facility Location Problems (Extended Abstract).
Covering Points in the Plane by <i>k</i>-Tours: Towards a Polynomial Time Approximation Scheme for General <i>k</i>.
A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence.
Private Information Storage (Extended Abstract).
Computationally Private Information Retrieval (Extended Abstract).
Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets.
A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes.
Using and Combining Predictors That Specialize.
On-Line Algorithms for Steiner Tree Problems (Extended Abstract).
Online Algorithms for Selective Multicast and Maximal Dense Trees.
Direct Product Results and the GCD Problem, in Old and New Communication Models.
The Linear-Array Problem in Communication Complexity Resolved.
Paul Erd&ouml;s (1913-1996): His Influence on the Theory of Computing.
Permanents, Pfaffian Orientations, and Even Directed Circuits (Extended Abstract).
Property Testing in Bounded Degree Graphs.
Exploring Unknown Environments.
On Floorplans of Planar Graphs.
Linear Zero-Knowledge - A Note on Efficient Zero-Knowledge Proofs and Arguments.
Commodity-Based Cryptography (Extended Abstract).
Oblivious Data Structures: Applications to Cryptography.
Is Linear Hashing Good?
A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP.
Improved Low-Degree Testing and its Applications.
Probabilistically Checkable Proofs with Zero Knowledge.
Making Games Short (Extended Abstract).
Improved Routing and Sorting on Multibutterflies.
Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (Preliminary Version).
On Sorting Strings in External Memory (Extended Abstract).
Pointer Jumping Requires Concurrent Read.
Lower Bounds for Distributed Coin-Flipping and Randomized Consensus.
Byzantine Quorum Systems.
All of Us are Smarter Than Any of Us: Wait-Free Hierarchies are not Robust.
The Decidability of Distributed Decision Tasks (Extended Abstract).
Two Algorithms for Nearest-Neighbor Search in High Dimensions.
Nearest Neighbor Queries in Metric Spaces.
Locality-Preserving Hashing in Multidimensional Spaces.
Incremental Clustering and Dynamic Information Retrieval.
A Constant-Factor Approximation Algorithm for Packet Routing, and Balancing Local vs. Global Criteria.
Universal <i>O</i>(Congestion + Dilation + log<sup>1+epsilon</sup><i>N</i>) Local Control Packet Switching Algorithms.
Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web.
Allocating Bandwidth for Bursty Connections.
The Swendsen-Wang Process Does Not Always Mix Rapidly.
Approximately Counting Up To Four (Extended Abstract).
An Interruptible Algorithm for Perfect Sampling via Markov Chains.
Sampling Lattice Points.
Page Replacement with Multi-Size Pages and Applications to Web Caching.
A polylog(<i>n</i>)-Competitive Algorithm for Metrical Task Systems.
On ACC<sup>0</sup>[<i>p<sup>k</sup></i>] Frege Proofs.
Reducing the Complexity of Reductions.
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.
Eigenvalues, Flows and Separators of Graphs.
Retraction of Probabilistic Computation and Linear Time.