Session 20

10:25-10:45 Asymptotically Good Codes Correcting Insertions, Deletions and Transpositions

Leonard J. Schulman, Georgia Institute of Technology; and David Zuckerman, University of Texas, Austin

10:50-11:10 Rounding in Lattices and Its Cryptographic Applications

Dan Boneh, Princeton University; and Ramarathnam Venkatesan, Bellcore

11:15-11:35 Approximating Matrix Multiplication for Pattern Recognition Tasks

Edith Cohen and David D. Lewis, AT&T Bell Laboratories

11:40-12:00 Improving the Discrepancy Bound for Sparse Matrices: Better Approximations for Sparse Lattice Approximation Problems

Aravind Srinivasan, National University of Singapore, Singapore

12:05-12:25 A Strong and Easily Computable Separation Bound for Arithmetic Expressions Involving Square Roots

Christoph Burnikel, Rudolf Fleischer, Kurt Mehlhorn, and Stefan Schirra, Max-Planck-Institute for Computer Science, Germany

Registration | Hotel Information | Transportation | Program-at-a-Glance | Author Index