In 2001, Papadimitriou was inducted as a Fellow of the Association for Computing Machinery and in 2002 he was awarded the Knuth Prize.
В 2001 году стал стипендиатом в Ассоциации вычислительной техники, в 2002 году награждён Премией Кнута.