Christos Papadimitriou
Christos Charilaos Papadimitriou (born August 16, 1949) is a Greek-American theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University.
Also recorded as Christos Harilaos Papadimitriou · Christos H. Papadimitriou · Christos Charilaos Papadimitriou
Christos Papadimitriou

Rama · CC BY-SA 2.0 fr
- Name
- Christos Papadimitriou
- Birth Name
- Christos Charilaos Papadimitriou
- Born
- 16 August 1949
- Birthplace
- Athens, Greece
- Education
- * National Technical University of Athens (MEng)
- Awards
- * Von Neumann Medal (2016)
- Nationality
- Greece · United States
- Occupation
- writer · mathematician · computer scientist · university teacher · musician
- Fields
- computer science
- Known for
- A simple algorithm for finding frequent elements in streams and bags
- Honours
- Knuth Prize · Gödel Prize · EATCS award · IEEE John von Neumann Medal · ACM Fellow · Harvey Prize
- Languages
- English · Modern Greek
VALÉORINE Encyclopedia
VALÉORINE documentary reading
Documentary summary
Christos Charilaos Papadimitriou (born August 16, 1949) is a Greek-American theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University.
Admitted source layer · organised and presented by VALÉORINE
Note VALÉORINE
No house-authored Note is published until its assertions and sources pass the VALÉORINE evidence contract. The documentary article remains available in full while that enrichment is being consolidated.
Documentary enrichment in progress · no unsupported statement published
Reference Check
Propose documentary evidence for Christos Papadimitriou. A contribution is never written directly as fact: identity, source, rights and evidence gates still decide.
Sign in to contribute
World of VALÉORINE
Documentary connections
Only confirmed graph relationships appear here. Images are shown only when their identity and reuse rights both pass the documentary gate.
Documentary evidence
Evidence Panel
not yet certified
- Identity
- resolved
- Independent source families
- 0
- Admitted assertions
- 0
- Open conflicts
- 0
Authority files
wikidata · Q92639 · wikipedia · Christos Papadimitriou
In this article
Biography
Biography
Christos Papadimitriou studied at Princeton University and National Technical University of Athens. The recorded working language is English and Modern Greek. The field of work recorded is computer science. Employment is recorded with Harvard University, Massachusetts Institute of Technology and University of California, Berkeley. Works named in the authority record are A simple algorithm for finding frequent elements in streams and bags. Distinctions recorded are Knuth Prize, Gödel Prize, EATCS award and IEEE John von Neumann Medal.

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

Professor Christos Papadimitriou giving a talk at the EPFL on 30 June 2009
Rama
Key facts
Key facts
• Name — Christos Papadimitriou • Birth Name — Christos Charilaos Papadimitriou • Born — 16 August 1949 • Birthplace — Athens, Greece • Fields — * Algorithms • Complexity • Game theory • Education • Evolution • Workplaces — * University of California, Berkeley • Columbia University • Harvard University • MIT • National Technical University of Athens • Stanford University • UCSD • Education — * National Technical University of Athens (MEng) • Princeton University (PhD) • Thesis Title — The Complexity of Combinatorial Optimization Problems • Thesis Url — http: dl.acm.org/citation.cfm?id=908113 • Thesis Year — 1976 • Doctoral Advisor — Kenneth Steiglitz • Doctoral Students — * Constantinos Daskalakis • Paris Kanellakis • Elias Koutsoupias • Joseph Mitchell • Christopher Umans • Yaron Singer • Awards — * Von Neumann Medal (2016) • EATCS Award (2015) • Gödel Prize (2012) • IEEE Computer Society Charles Babbage Award (2004) • Knuth Prize (2002) • Website — http: www.cs.berkeley.edu/~christos
Education
Education
Papadimitriou studied at the National Technical University of Athens, where in 1972 he received a degree in electrical engineering through an integrated master's program. He then pursued graduate studies at Princeton University, where he received his PhD in electrical engineering and computer science in 1976 after completing a doctoral dissertation titled "The complexity of combinatorial optimization problems."
Career
Career
Papadimitriou has taught at Harvard, MIT, the National Technical University of Athens, Stanford, UCSD, University of California, Berkeley and is currently the Donovan Family Professor of Computer Science at Columbia University. Papadimitriou co-authored a paper on pancake sorting with Bill Gates, then a Harvard undergraduate. Papadimitriou recalled "Two years later, I called to tell him our paper had been accepted to a fine math journal. He sounded eminently disinterested. He had moved to Albuquerque, New Mexico to run a small company writing code for microprocessors, of all things. I remember thinking: 'Such a brilliant kid. What a waste.'" The company was Microsoft. Papadimitriou co-authored "The Complexity of Computing a Nash Equilibrium" with his students Constantinos Daskalakis and Paul W. Goldberg, for which they received the 2008 Kalai Game Theory and Computer Science Prize from the Game Theory Society for "the best paper at the interface of game theory and computer science", in particular "for its key conceptual and technical contributions"; and the Outstanding Paper Prize from the Society for Industrial and Applied Mathematics. In 2001, Papadimitriou was inducted as a Fellow of the Association for Computing Machinery and in 2002 he was awarded the Knuth Prize. Also in 2002, he became a member of the U.S. National Academy of Engineering for contributions to complexity theory, database theory, and combinatorial optimization. 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. In 2012, he, along with Elias Koutsoupias, was awarded the Gödel Prize for their joint work on the concept of the price of anarchy. 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.
Personal life
Personal life
At UC Berkeley, in 2006, he joined a professor-and-graduate-student band called Lady X and The Positive Eigenvalues.
Career and activity
Career and activity
Christos Papadimitriou worked in computer science. He was employed by Harvard University, Massachusetts Institute of Technology, University of California, Berkeley, University of California, San Diego and Stanford University. He belonged to National Academy of Sciences, American Academy of Arts and Sciences, National Academy of Engineering, Association for Computing Machinery and Academia Europaea.
Identity
Identity
Christos Papadimitriou is recorded with the occupation university teacher. Recorded with the occupation computer scientist. Recorded with the occupation prose writer. Recorded as writer, mathematician, computer scientist, university teacher and musician.
Life and career
Dated record
Life and career
The full dated record · 1 entries
1949
Christos Papadimitriou was born on 16 August 1949.
Publications
• 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 2008 • 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. • He co-authored a paper with Bill Gates, co-founder of Microsoft, on pancake sorting.
Honors and awards
In 1997, Papadimitriou received a doctorate honoris causa from the ETH Zurich. In 2011, Papadimitriou received a doctorate honoris causa from the National Technical University of Athens. In 2013, Papadimitriou received a doctorate honoris causa from the École polytechnique fédérale de Lausanne (EPFL). Papadimitriou was awarded the IEEE John von Neumann Medal in 2016, the EATCS Award in 2015, the Gödel Prize in 2012, the IEEE Computer Society Charles Babbage Award in 2004, and the Knuth Prize in 2002. In 2019 he received the Harvey Prize of the Technion/Israel for the year 2018.
Notes from the source article
Cited by Wikipedia
Notes from the source article
These works are cited by the source article, in its own numbering. They are recorded as its citations, not as sources VALÉORINE has verified.
- 1.Columbia Faculty.
- 2.MathGenealogy id=46289
- 3.Christos Papadimitriou. 24 May 2018.
- 4.Ahmed, F. Profile of Christos Papadimitriou. Proceedings of the National Academy of Sciences. 111. 45. 15858–60. 2014. 10.1073/pnas.1405579111.
- 5.The complexity of combinatorial optimization problems. 1976.
- 6.People of ACM – Christos Papadimitriou. People of ACM.
- 7.Game Theory Society: Named Lectures and Prizes. www.gametheorysociety.org.
- 8.Prize in Game Theory and Computer Science of the Game Theory Society (2008).
- 9.Member Directory at NAE Website.
- 10.Special Events: Honoring Christos Papadimitriou Scientific Contribution to Computer Science. ICALP 2009 – 36th International Colloquium on Automata, Languages and Programming.
- 11.Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory. 16 May 2012.
- 12.Logicomix
- 13.Honorary Doctorates, Department of Computer Science.
- 14.Live feed from the Award Ceremony of an honorary doctorate from the NTUA to the UC Berkeley Professor Chr. Papadimitriou.
- 15.Harvey Prize 2018
- 16.Gates, William H. Bounds for sorting by prefix reversal. Discrete Mathematics. 27. 47–57. 1979. 10.1016/0012-365X(79)90068-2.
- 17.Engineers rock — Out of the EECS department comes a hot new band.
References
Citations
References
Each reference names the institution holding it, so a reader may go to the document itself.
reference work
Wikidata, structured authority record Q92639: Christos PapadimitriouWikimedia Foundation
Partially resolvedreference work
Partially resolved
People, houses and institutions
Knowledge graph
People, houses and institutions
Teachers, collaborators, publishers and institutions recorded against this person, each on a stated basis.
Studied at
1- Princeton UniversityOrganisation
Established from a fact already recorded on a verified source.
Further particulars
Held on the record
Further particulars
Open the remaining particulars
The authorities additionally record the headings Christos Harilaos Papadimitriou, Christos H. Papadimitriou and Christos Charilaos Papadimitriou. His recorded languages were English, Modern Greek and Greek. Formation and teaching. Papadimitriou studied at Princeton University and National Technical University of Athens. The record notes the qualification Doctor of Philosophy. Papadimitriou received Knuth Prize, Gödel Prize, EATCS award, IEEE John von Neumann Medal, ACM Fellow and Harvey Prize.
Identity and origins
Recognition and collections
The Encyclopedia exists whether or not anything is for sale. Corrections are recorded rather than overwritten, and every version of this record is kept. Published 14 August 2026.
Elsewhere in Books
38,960 published records in this field, each with its sources named.
- Christopher WhyteAuthor
- Christophoros LiontakisAuthor
- Christos ChristovasilisAuthor
- Christos LaskarisAuthor
- Christos SartzetakisAuthor
- Christos TsiolkasAuthor
- Christos YannarasAuthor
- ChrodegangAuthor
Best supported in this field
For owners
Own a work by Christos Papadimitriou?
A specialist will read what you send and tell you what the house can establish, what it cannot, and whether the object is suited to sale. There is no charge and no obligation. The object stays with you throughout; nothing is shipped to us unless it is arranged in writing beforehand.