Theory of Computing
Computational Complexity Theory
“Separation of Complexity Classes”. Journal of the ACM, Fiftieth Anniversary Special Issue 50(1): 58–62 (January 2003).
Selected Awards and Honors
- Grand Medal, Latvian Academy of Science, 2001.
- CRA Distinguished Service Award, 2000.
- Doctor of Science (honoris causa), University of Missouri, Kansas City, 1999.
- B. Bolzano Gold Medal of the Academy of Science, Czech Republic, 1995.
- Doctor of Science (honoris causa), University of Dortmund, Germany, 1995.
- Turing Award Winner, 1993