Manuel Blum
ACM Fellows
USA - 2020
citation
For contributions to the foundations of computational complexity theory and its application to cryptography and program checking
Press ReleaseACM A. M. Turing Award
USA - 1995
READ FULL CITATION AND ESSAYcitation
In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking.
Starting from his early work on the inherent limitations of computing devices, Dr. Blum's research has developed around a single unifying theme: finding positive, practical consequences of living in a world where all computational resources are bounded. Dr. Blum shows that secure business transactions, pseudo-random number generation, and program checking are all possible precisely because all computational devices are resource bounded.
Dr. Blum is one of the founders of computational complexity theory, a field that is central to theoretical computer science, and one which deals with measuring the difficulty of performing computations. His work on machine-independent complexity yields a theory of computational cost that is relevant also to practical problems. Cyptographic protocols which are used in the transmission of sensitive information are secure because they can be shown to be difficult to break. Thus, an intruder cannot determine the information in a cryptograhically encoded message without going through an inordinately complex computation that would be prohibitively costly and time consuming to perform. For computer programs it is very difficult to develop perfectly error-free programs. In this area Dr. Blum has shown how his techniques can be applied to make programs more reliable, and to check their results. Since this work is very fundamental one can expect that it will find application to many other practical problems as well.