Christos Papadimitriou
Encyclopedia
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.
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. 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.
Greek language
Greek is an independent branch of the Indo-European family of languages. Native to the southern Balkans, it has the longest documented history of any Indo-European language, spanning 34 centuries of written records. Its writing system has been the Greek alphabet for the majority of its history;...
: Χρίστος Χαρίλαος Παπαδημητρίου; born August 16, 1949, Athens
Athens
Athens , is the capital and largest city of Greece. Athens dominates the Attica region and is one of the world's oldest cities, as its recorded history spans around 3,400 years. Classical Athens was a powerful city-state...
) is a Professor
Professor
A professor is a scholarly teacher; the precise meaning of the term varies by country. Literally, professor derives from Latin as a "person who professes" being usually an expert in arts or sciences; a teacher of high rank...
in the Computer Science Division at the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
, United States
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
. He studied at the National Technical University of Athens
National Technical University of Athens
The National Technical University of Athens , sometimes simply known as Athens Polytechnic, is among the oldest and most prestigious higher education institutions of Greece....
(BS
Bachelor of Science
A Bachelor of Science is an undergraduate academic degree awarded for completed courses that generally last three to five years .-Australia:In Australia, the BSc is a 3 year degree, offered from 1st year on...
in Electrical Engineering
Electrical engineering
Electrical engineering is a field of engineering that generally deals with the study and application of electricity, electronics and electromagnetism. The field first became an identifiable occupation in the late nineteenth century after commercialization of the electric telegraph and electrical...
, 1972) and at Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
(MS
Master of Science
A Master of Science is a postgraduate academic master's degree awarded by universities in many countries. The degree is typically studied for in the sciences including the social sciences.-Brazil, Argentina and Uruguay:...
in Electrical Engineering, 1974 and PhD
PHD
PHD may refer to:*Ph.D., a doctorate of philosophy*Ph.D. , a 1980s British group*PHD finger, a protein sequence*PHD Mountain Software, an outdoor clothing and equipment company*PhD Docbook renderer, an XML renderer...
in Electrical Engineering and Computer Science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, 1976). He has also taught at Harvard, MIT, the National Technical University of Athens
National Technical University of Athens
The National Technical University of Athens , sometimes simply known as Athens Polytechnic, is among the oldest and most prestigious higher education institutions of Greece....
, 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
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
. He has also co-authored the textbook Algorithms (2006) with Sanjoy Dasgupta and Umesh Vazirani
Umesh Vazirani
Umesh Virkumar Vazirani is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. Vazirani was himself a Ph.D. student at Berkeley, receiving his Ph.D. in 1986 under the...
, and the graphic novel Logicomix
Logicomix
Logicomix: An Epic Search for Truth is a graphic novel about the foundational quest in mathematics, written by Apostolos Doxiadis, author of Uncle Petros and Goldbach's Conjecture, and theoretical computer scientist Christos Papadimitriou of the University of California, Berkeley. Character design...
(2009) with Apostolos Doxiadis
Apostolos Doxiadis
Apostolos Doxiadis is a Greek writer.Since his early years Doxiadis was drawn to mathematics and at the age of 15 he entered Columbia University in New York City to study maths...
.
His name was listed in the 19th position on the CiteSeer
CiteSeer
CiteSeer was a public search engine and digital library for scientific and academic papers. It is often considered to be the first automated citation indexing system and was considered a predecessor of academic search tools such as Google Scholar and Microsoft Academic Search. It was replaced by...
search engine academic database and digital library.
Awards and honors
In 2001, Papadimitriou was inducted as a FellowFellow
A fellow in the broadest sense is someone who is an equal or a comrade. The term fellow is also used to describe a person, particularly by those in the upper social classes. It is most often used in an academic context: a fellow is often part of an elite group of learned people who are awarded...
of the Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
and in 2002 he was awarded the Knuth Prize
Knuth Prize
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.-History:...
. He became fellow of the US National Academy of Engineering
National Academy of Engineering
The National Academy of Engineering is a government-created non-profit institution in the United States, that was founded in 1964 under the same congressional act that led to the founding of the National Academy of Sciences...
for contributions to complexity theory, database theory, and combinatorial optimization. In 2009 he was elected to the US National Academy of Sciences
United States National Academy of Sciences
The National Academy of Sciences is a corporation in the United States whose members serve pro bono as "advisers to the nation on science, engineering, and medicine." As a national academy, new members of the organization are elected annually by current members, based on their distinguished and...
. During the 36th International Colloquium on Automata, Languages and Programming
International Colloquium on Automata, Languages and Programming
ICALP, the International Colloquium on Automata, Languages and Programming is an academic conference organized annually by the European Association for Theoretical Computer Science and held in different locations around Europe...
(ICALP 2009), there was a special event honoring Papadimitriou's contributions to computer science.
Interesting facts
- He co-authored a paper with Bill GatesBill GatesWilliam Henry "Bill" Gates III is an American business magnate, investor, philanthropist, and author. Gates is the former CEO and current chairman of Microsoft, the software company he founded with Paul Allen...
, co-founder of MicrosoftMicrosoftMicrosoft Corporation is an American public multinational corporation headquartered in Redmond, Washington, USA that develops, manufactures, licenses, and supports a wide range of products and services predominantly related to computing through its various product divisions...
, while Gates was studying at Harvard. - At UC Berkeley, in 2006, he joined a professor-and-graduate-student band called Lady X and The Positive Eigenvalues.