In September 2009, Fortnow brought mainstream attention to complexity theory when he published an article surveying the progress made in the P versus NP problem in Communications of the Association for Computing Machinery.
While still a graduate student at MIT, Fortnow showed that there are no perfect zero-knowledge protocols for NP-complete languages unless the polynomial hierarchy collapses.
[11] In November 1989, Fortnow received an email from Noam Nisan showing that co-NP had multiple prover interactive proofs (MIP).
[13] Quickly following up on this (January 17, 1990, less than two months after receiving Nisan's email) Fortnow, along with László Babai and Carsten Lund, proved that MIP=NEXP.
[14] These algebraic techniques were expanded further by Fortnow, Babai, Leonid Levin and Mario Szegedy when they presented a new generic mechanism for checking computations.
[15] Fortnow has continued to publish on a variety of topics in the field of computational complexity including derandomization, sparse languages, and oracle machines.