1995 · Theory & algorithms
Complexity theory also supplied tools for checking and protecting computation.
Visual guide
Specify a computation and its cost.
Ask a carefully chosen question.
Use evidence to assess the result.
Theoretical limits and rigorous verification methods became tools for dependable and secure computing.
Different checking methods offer different guarantees; a successful check is meaningful only under its stated assumptions.
01 · The idea
Manuel Blum developed fundamental results about computational complexity and brought those ideas into cryptography and program checking. A key theme is that understanding the resources a computation requires can be useful even when the goal is to verify or protect it rather than simply run it.
Theoretical limits and rigorous verification methods became tools for dependable and secure computing.
02 · The people
Manuel Blum developed deep ideas about the complexity and reliability of computation. His axiomatic approach clarified what it means to measure computational resources, while later work addressed program checking, pseudorandomness, and cryptography. At Berkeley, he helped build a strong community in theoretical computer science. His research repeatedly asked how limited computation can still provide useful guarantees, influencing both abstract theory and practical methods for trustworthy computing.
Read the biography ↗03 · Read further
Original explanations based on the official award record. The subject label is an editorial navigation aid.
Complexity theory connected random choices with some of computation’s deepest limits.
The story
Numerical libraries connect mathematical algorithms with changing hardware.
The story