Brian A. LaMacchia
Department of Electrical Engineering and Computer Science
Massachusetts Institute of Technology
|Thesis Supervisor:||Silvio Micali|
|Associate Professor of Computer Science and Engineering|
|Company Supervisor:||Andrew M. Odlyzko|
|AT&T Bell Laboratories|
First, my sincerest thanks to Andrew M. Odlyzko, my company supervisor at AT&T Bell Laboratories. This thesis would not have been begun, let alone finished, without Andrew's guidance. Throughout my time at Bell Labs Andrew has been my supervisor, mentor and friend; his initial suggestion that I look at applications of Seysen's algorithm to subset sum problems was the basis for this work. Andrew's support and encouragement were without bound.
I also thank Matthijs J. Coster for his assistance throughout this project. Matthijs suggested numerous variants of Seysen's algorithm and helped design Algorithm SL for solving subset sum problems. His comments on early drafts of this thesis were also quite helpful.
Many people have commented on different aspects of this project while work was in progress. In particular, I'd like to thank Jeff Lagarias, Claus Schnorr and Warren Smith for their assistance.
This work was performed under the auspices of the Center for Mathematical Sciences Research at AT&T Bell Laboratories. I thank Mike Garey, director, and the other members of the Math Center for the research environment they maintain and their constant support during my tenure at Bell Labs.
Many thanks to Professor Silvio Micali, my thesis supervisor at MIT, for overseeing this work. Silvio's enthusiasm for this project never wavered, and his comments when I began writing this thesis were very useful.
Thanks also Professors Harold Abelson and Gerald J. Sussman, and the members of Project MAC (Mathematics and Computation), for their support upon my return from Bell Labs. In particular, thanks to Andy Berlin, Elizabeth Bradley, Mike Eisenberg, Mark Freidman, Arthur Gleckler, Chris Hanson, Stefan Kozlowski, Bill Rozas, Sameer Shalaby, Thanos Siapas, Panayotis Skordos, Franklyn Turbak, Henry Wu, and Feng Zhao. They are a very special group of people.
This project was performed as part of the MIT VI-A Internship Program. The director of the VI-A Program is Kevin O'Toole. Professor Frederic Morgenthaler serves as faculty liaison between the VI-A Office and AT&T Bell Laboratories. At Bell Labs, the VI-A Program is administered by J. Michael Milner and José L. Reyes. My thanks to all of them for making VI-A at Bell Labs so successful.
This paper describes research conducted at AT&T Bell
Laboratories, as part of the MIT VI-A Internship Program, and at the
Artificial Intelligence Laboratory of the Massachusetts Institute of
Technology. Support for the Laboratory's artificial intelligence
research is provided in part by the Advanced Research Projects Agency of
the Department of Defense under Office of Naval Research contract