94 On the Limits of Non-Approximability of Lattice Problems.
135 The Shortest Vector Problem in <i>L<sub>2</sub></i> is <i>NP</i>-hard for Randomized Reductions (Extended Abstract).
104 Quantum Circuits with Mixed States.
25 Exact Sampling and Approximate Counting Techniques.
12 A Polynomial Approximation Algorithm for the Minimum Fill-In Problem.
56 An Improved Approximation Algorithm for Multiway Cut.
91 A Framework for Fast Quantum Mechanical Algorithms.
138 Quantum vs. Classical Communication and Computation.
26 Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching.
123 Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity.
80 Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract).
32 Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems.
131 Approximation Schemes for Euclidean <i>k</i>-Medians and Related Problems.
80 Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and <i>k</i>-Median.
3 One Help Bit Doesn't Help.
45 Perfectly One-Way Probabilistic Hash Functions (Preliminary Version).
60 Non-Interactive and Non-Malleable Commitment.
120 Protecting Data Privacy in Private Information Retrieval Schemes.
200 On Approximating Arbitrary Metrices by Tree Metrics.
12 Trees and Euclidean Metrics.
3 Random Generation of Embedded Graphs and an Extension to Dobrushin Uniqueness (Extended Abstract).
20 Efficient Algorithms for Constructing Fault-Tolerant Geometric Spanners.
28 Almost Optimal Dispersers.
17 NP Might Not Be As Easy As Detecting Unique Solutions.
340 The Random Oracle Methodology, Revisited (Preliminary Version).
9 Randomized Complexity Lower Bounds.
39 Weak Alternating Automata and Tree Automata Emptiness.
23 Over Words, Two Variables Are as Powerful as One Quantifier Alternation.
22 Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound.
392 Analysis of Low Density Codes and Improved Designs Using Irregular Graphs.
96 Spot-Checkers.
55 The Power of a Pebble: Exploring and Mapping Directed Graphs.
32 Linear-Time Pointer-Machine Algorithms for Least Common Ancestors, MST Verification, and Dominators.
48 A Sublinear Bipartiteness Tester for Bunded Degree Graphs.
27 Recycling Queries in PCPs and in Linearity Tests (Extended Abstract).
26 The Closure of Monadic NP (Extended Abstract).
0 Information Theoretic Implications for Pairing Heaps.
142 Min-Wise Independent Permutations (Extended Abstract).
19 The Approximability of NP-hard Problems.
18 Algorithms for Capacitated Vehicle Routing.
49 Adaptive Packet Routing for Bursty Adversarial Traffic.
7 Stability Results for Networks with Input and Output Blocking.
22 Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks.
17 TCP Dynamic Acknowledgment Delay: Theory and Practice (Extended Abstract).
47 Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge.
182 Concurrent Zero-Knowledge.
202 A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols (Extended Abstract).
17 A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs.
19 Checking Polynomial Identities over any Field: Towards a Derandomization?
63 Multicasting in Heterogeneous Networks.
53 Minimizing Stall Time in Single and Parallel Disk Systems.
22 On Indexed Data Broadcast.
74 Segmentation Problems.
6 Computing Local Dimension of a Semialgebraic Set.
24 Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations.
0 A Black Box Approach to the Algebraic Set Decomposition Problem.
14 Are Lower Bounds Easier over the Reals?
39 Planar Map Graphs.
36 Further Algorithmic Aspects of the Local Lemma.
14 Decision Algorithms for Unsplittable Flow and the Half-Disjoint Paths Problem.
71 Approximating Geometrical Graphs via "Spanners" and "Banyans".
34 Finding Almost-Satisfying Assignments.
81 On the Complexity of Unsatisfiability Proofs for Random <i>k</i>-CNF Formulas.
5 <i>K</i>-sat on Groups and Undecidability.
16 An Exponential Lower Bound for Depth 3 Arithmetic Circuits.
6 A New Composition Theorem for Learning Algorithms.
21 Adaptive versus Nonadaptive Attribute-Efficient Learning.
131 On the Complexity of Protein Folding (Extended Abstract).
414 Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.
171 Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces.
24 Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract).
25 On Broadcast Disk Paging.
49 A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents.
25 On Separating the Read-k-Times Branching Program Hierarchy.
102 Robust Efficient Distributed RSA-Key Generation.
23 The Cost of the Missing Bit: Communication Complexity with Help.