Christos Papadimitriou

Christos Papadimitriou
Professor Christos Papadimitriou giving a talk at the EPFL on 30 June 2009.

Christos Harilaos Papadimitriou (Greek: Χρίστος Χαρίλαος Παπαδημητρίου; born August 16, 1949, Athens) is a Professor in the Computer Science Division at the University of California, Berkeley, United States. He studied at the National Technical University of Athens (BS in Electrical Engineering, 1972) and at Princeton University (MS in Electrical Engineering, 1974 and PhD in Electrical Engineering and Computer Science, 1976). He has also taught at Harvard, MIT, the National Technical University of Athens, Stanford, and UCSD.

Papadimitriou is the author of the textbook Computational Complexity, one of the most widely used textbooks in the field of computational complexity theory. He has also co-authored the textbook Algorithms (2006) with Sanjoy Dasgupta and Umesh Vazirani, and the graphic novel Logicomix (2009) with Apostolos Doxiadis.

His name was listed in the 19th position on the CiteSeer search engine academic database and digital library.


Awards and honors

In 2001, Papadimitriou was inducted as a Fellow of the Association for Computing Machinery and in 2002 he was awarded the Knuth Prize. He became fellow of the US National Academy of Engineering for contributions to complexity theory, database theory, and combinatorial optimization.[1] In 2009 he was elected to the US National Academy of Sciences. During the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), there was a special event honoring Papadimitriou's contributions to computer science.[2]

Interesting facts


  • Elements of the Theory of Computation (with Harry R. Lewis). Prentice-Hall, 1982; second edition September 1997.
  • Combinatorial Optimization: Algorithms and Complexity (with Kenneth Steiglitz). Prentice-Hall, 1982; second edition, Dover, 1998.
  • The Theory of Database Concurrency Control. CS Press, 1986.
  • Computational Complexity. Addison Wesley, 1994.
  • Turing (a Novel about Computation). MIT Press, November 2003.
  • Life Sentence to Hackers? (in Greek). Kastaniotis Editions, 2004. A compilation of articles written for the Greek newspaper To Vima.
  • Algorithms (coauthored with Sanjoy Dasgupta and Umesh Vazirani). McGraw-Hill, September 2006
  • Logicomix, An Epic Search for Truth (coauthored with Apostolos Doxiadis, with artwork by Alecos Papadatos and Annie di Donna). Bloomsbury Publishing and Bloomsbury USA, September 2009.


  1. ^ National Academy of Engineering, Members by Last Name: P
  2. ^ "Special Events: Honoring Christos Papadimitriou Scientific Contribution to Computer Science". ICALP 2009 – 36th International Colloquium on Automata, Languages and Programming. 
  3. ^ Gates W.H.; Papadimitriou, C.H. Bounds for sorting by prefix reversal. Discrete Math. 27 (1979), 47–57.

External links

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Christos Papadimitriou — es un profesor de la división de ciencias de la computación en la Universidad de California, Berkeley. Estudió en la Universidad Politécnica Nacional de Atenas (BS en Ingeniería eléctrica, 1972) y en la Universidad de Princeton (Maestría en… …   Wikipedia Español

  • Christos Papadimitriou — Christos Charilaos Papadimitriou (griechisch Χρήστος Χαρίλαος Παπαδημητρίου) (* 1949 in Athen) ist ein griechischer Informatiker. Papadimitriou 2009 Papadimitriou machte 1972 sein Diplom in Elektrotechnik an der …   Deutsch Wikipedia

  • Papadimitriou — may refer to:* Thodoros Papadimitriou (born 1931), Greek sculptor * Alexandros Papadimitriou (born 1973), Greek Olympic hammer thrower * Arthur Papadimitriou, Australian art collector * Christos Papadimitriou, U.S. computer scientist * Lefteris… …   Wikipedia

  • Papadimitriou — ist der Name folgender Personen: Alexandros Papadimitriou (* 1973), griechischer Hammerwerfer Christos Papadimitriou (* 1949), griechischer Informatiker Diese Seite ist eine Begriffsklärung zur Unterscheidung mehrere …   Deutsch Wikipedia

  • List of Greeks — This is a list of Greek people. Actors/actressesAncient period*Metrobius *ThespisModern period*Alekos Alexandrakis *Criss Angel *Jennifer Aniston *Yannis Bezos *Michael Chiklis *Cybele *Georges Corraface *Jacques Damala *Rika Diallina *Lavrentis… …   Wikipedia

  • Pancake sorting — is a variation of the sorting problem in which the only allowed operation is to reverse the elements of some prefix of the sequence. Unlike a traditional sorting algorithm, which attempts to sort with the least comparisons possible, the goal is… …   Wikipedia

  • Non-deterministic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Mihalis Yannakakis — Born September 13, 1953 …   Wikipedia

  • PPAD (complexity) — PPAD is a complexity class, standing for Polynomial Parity Arguments on Directed graphs . Introduced by Christos Papadimitriou in 1994, PPAD is a subclass of TFNP based on functions that can be shown to be total by a parity argument. [cite… …   Wikipedia

  • Bill Gates — For other people named Bill Gates, see Bill Gates (disambiguation). Bill Gates …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”