Subset Sum Problems

by

Brian A. LaMacchia

Artificial Intelligence Laboratory

and

Department of Electrical Engineering and Computer Science

Massachusetts Institute of Technology

This thesis investigates a new approach to lattice basis reduction
suggested by M. Seysen. Seysen's algorithm attempts to globally reduce
a lattice basis, whereas the Lenstra, Lenstra, Lovász (LLL) family of
reduction algorithms concentrates on local reductions. We show that
Seysen's algorithm is well suited for reducing certain classes of
lattice bases, and often requires much less time in practice than the
LLL algorithm. We also demonstrate how Seysen's algorithm for basis
reduction may be applied to subset sum problems. Seysen's technique,
used in combination with the LLL algorithm, and other heuristics,
enables us to solve a much larger class of subset sum problems than was
previously possible.

This report is a revised version of a thesis submitted in partial fulfillment of the requirements for the degree of Master of Science in the Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology in May, 1991.

Thesis Supervisor: | Silvio Micali |

Associate Professor of Computer Science and Engineering | |

Company Supervisor: | Andrew M. Odlyzko |

AT&T Bell Laboratories |

This report is a revised version of a thesis submitted in partial fulfillment of the requirements for the degree of Master of Science in the Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology in May, 1991.

This thesis could not have been completed without the support of a great many people. I wish to take this opportunity to express my appreciation for their help throughout this project.

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
N00014-89-J-3202.

- Contents
- List of Tables
- List of Figures
- Introduction
- The Seysen Basis Reduction Algorithm
- Solving Subset Sum Problems
- Conclusions
- Bibliography
- About this document ...