I give below only a brief high-level description of the main result in each paper.
Adler and Maggs study the problem of communication between a client and a server across an asymmetric channel. They demonstrate scenarios where a highspeed link from the server to the client can be used to greatly reduce the number of bits sent from the client to the server across a slower link.
Beame, Jayram, and Saks study time-space trade-off lower bounds for Boolean functions with a single output bit. They provide the first nontrivial lower bound for this class of functions on general branching programs.
Feige and Kilian consider the problem of finding large independent sets in a semirandom graph, which is essentially a graph constructed via a blending of random and adversarial decisions. They develop a heuristic algorithm for extracting the independent set and apply it to improving coloring algorithms for semirandom graphs.
Fernandez de la Vega and Kenyon devise a randomized polynomial time approximation scheme for the metric MAX-CUT problem. In this problem, the goal is to partition points in a metric space into two parts to maximize the sum of distances between points in distinct parts.
Impagliazzo, Paturi, and Zane consider the relative likelihood of subexponential time algorithms for NP-complete problems. They introduce a notion of subexponential reduction family and establish completeness results with respect to such reductions.
Impagliazzo and Wigderson establish the result that if BPP ] EXP, then every problem in BPP can be solved deterministically in subexponential time on almost every input. This is the first derandomization of BPP based on uniform, noncryptographic hardness assumptions.
Indyk provides an efficient data structure for supporting approximate nearest neighbor queries under the L . norm. His data structure is the first to provide good approximation with near-linear processing and subexponential space for this metric.
Russell and Zuckerman consider the leader election problem-n players wish to elect a random leader using a process that is robust against a coalition of the players attempting to bias the outcome. In the perfect information model, they provide a protocol that achieves this goal in log* n+O(1) rounds.
Umans resolves the following conjecture due to Stockmeyer: The minimum Equivalent DNF problem is S p 2 -complete. I thank the authors for agreeing to submit their papers to this special issue. I am equally grateful to the (anonymous) reviewers for their hard work in reviewing the papers. Finally, my thanks to Ed Blum and the editorial staff of this journal for their support.