Franco P. Preparata
|Franco P. Preparata|
University of Illinois at Urbana-Champaign
|Alma mater||University of Rome|
|Doctoral students||Der-Tsai Lee
Nancy M. Amato
|Known for||computational geometry|
|Notable awards||ACM Fellow (1995)
IEEE Fellow (1978)
He is best known for his 1985 book "Computational Geometry: An Introduction" into which he blended salient parts of M. I. Shamos' doctoral thesis (Shamos appears as a co-author of the book). This book, which represents a snapshot of the disciplines as of 1985, has been for many years the standard textbook in the field, and has been translated into four foreign Languages (Russian, Japanese, Chinese, and Polish). He has made several contributions to the computational geometry, the most recent being the notion of "algorithmic degree" as a key feature to control robust implementations of geometric algorithms.
In addition, Preparata has worked in many other areas of, or closely related to, computer science.
His initial work was in coding theory, where he (independently and simultaneously) contributed the Berlekamp-Preparata codes (optimal convolution codes for burst-error correction) and the Preparata codes, the first known systematic class of nonlinear binary codes, with higher information content than corresponding linear BCH codes of the same length. Thirty years later these codes have been found relevant to quantum coding theory.
In 1967, he substantially contributed to a model of system-level fault diagnosis, known today as the PMC (Preparata-Metze-Chien) model, which is a main issue in the design of highly dependable processing systems. This model is still the object of intense research today (as attested by the literature).
Over the years, he was also active in research in parallel computation and VLSI theory. His 1979 paper (with J. Vuillemin), still highly cited, presented the cube-connected-cycles (CCC), a parallel architecture that optimally emulates the hypercube interconnection. This interconnection was closely reflected in the architecture of the CM2 of Thinking Machines Inc., the first massive-parallel system in the VLSI era. His 1991 paper with Zhou and Kang on interconnection delays in VLSI was awarded the 1993 "Darlington Best Paper Award" by the IEEE Circuits and Systems Society. In the late nineties, (in joint work with G. Bilardi) he confronted the problem of the physical limitations (space and speed) of parallel computation, and formulated the conclusion that mesh connections are ultimately the only scalable massively parallel architectures.
More recently the focus of his research has been Computational Biology. Among other results, he contributed (with Eli Upfal) a novel approach to DNA Sequencing by Hybridization, achieving sequencing lengths that are the square of what was previously known, which has attracted media coverage.
The unifying character of these results in diverse research areas is the methodological approach, based on the construction of precise mathematical models and the use of sophisticated mathematical techniques.
Preparata was born in Italy in December, 1935. He received a doctorate from the University of Rome, Italy in 1959. After a postdoctorate at CNR and several years of working in industry, he joined the faculty of the University of Illinois at Urbana-Champaign in 1965, where he achieved the rank of Professor in 1970. He stayed at the UIUC for many years, advising 16 Ph.D. students there. He received his Italian Libera Docenza in 1969. In 1991, Preparata moved from Illinois to Brown University where he has remained active in research, teaching, and student advising until his retirement at the end of 2013. He is the author (or co-author) of three books and nearly 250 articles. In 1997, the University of Padova awarded Preparata an honorary doctorate in Information Engineering. Preparata is an IEEE Fellow (1978),an ACM Fellow (1993), and was a Fellow of the Japan Society for the Advancement of Science.
- Preparata, Franco P.; Metze, G.; Chien, R. T. (1967). "On the Connection Assignment Problem of Diagnosable Systems". IEEE Transactions on Electronic Computers. EC-16 (6): 848–854. doi:10.1109/PGEC.1967.264748.
- Franco P. Preparata, Raymond T. Yeh, Introduction to Discrete Structures for Computer Science and Engineering (Addison-Wesley series in computer science and information processing), 1973, ISBN 0-201-05968-1
- Preparata, Franco P.; Shamos, Michael I. (1985). Computational Geometry. Monographs in Computer Science. Springer-Verlag. ISBN 978-0-387-96131-6. OCLC 11970840. ISBN 9783540961314 (1988, 2nd printing, expanded and corrected, 1990).
- Preparata, Franco P.; Vuillemin, Jean (1981). "The cube-connected cycles: a versatile network for parallel computation". Communications of the ACM. 24 (5): 300–309. doi:10.1145/358645.358660.
- Zhou, D.; Preparata, Franco P.; Kang, Sung Mo (1991). "Interconnection delay in very high-speed VLSI". IEEE Transactions on Circuits and Systems. 38 (7): 779–790. doi:10.1109/31.135749.
- Preparata, Franco P.; Shamos, Michael Ian. Computational Geometry - Springer. doi:10.1007/978-1-4612-1098-6.
- Preparata, Franco P.; Upfal, Eli (2000-08-01). "Sequencing-by-Hybridization at the Information-Theory Bound: An Optimal Algorithm". Journal of Computational Biology. 7 (3-4): 621–630. doi:10.1089/106652700750050970. ISSN 1066-5277. PMID 11108482.