Papadimitriou is the author of the textbook Computational Complexity, one of the most widely used textbooks in the field of computational complexity theory.
Papadimitriou este autor al manualului Computation Complexity, unul dintre cele mai utilizate manuale în domeniul teoriei complexității.