Author bio

Christos H. Papadimitriou

Christos H. Papadimitriou - book author

Christos Harilaos Papadimitriou (Greek: Χρίστος Χ. Παπαδημητρίου) is a Professor in the Computer Science Division at the University of California, Berkeley, United States.
Papadimitriou is the author of the textbook Computational Complexity and has co-authored Algorithms with Sanjoy Dasgupta and Umesh Vazirani.
He has collaborated with Apostolos Doxiadis on the graphic novel Logicomix, and has published one novel, Turing.

Christos H. Papadimitriou is the author of books: Computational Complexity, Combinatorial Optimization: Algorithms and Complexity, Turing: A Novel about Computation, The Theory Of Database Concurrency Control, Elements of the Theory of Computation, Internet and Network Economics: 4th International Workshop, Wine 2008, Shanghai, China, December 17-20, 2008. Proceedings, Theory Of Db Concurr Con 27 1: 21 Questions, Logicomix: An Epic Search for Truth, Kurt G�del and the Foundations of Mathematics: Horizons of Truth, Ισόβια στους χάκερ; Απόψεις για το ίντερνετ, την επιστήμη και όλα τα υπόλοιπα

Author books

This modern introduction to the Theory of Computer Science is the first unified introduction to Computational Complexity. It offers a comprehensive and accessible treatment of the theory of algorithms and complexity—the elegant body of concepts and methods developed by computer scientists over the past 30 years for studying the performance and limitations of computer algorithms. The book is self-contained in that it develops all necessary mathematical prerequisites from such diverse fields such as computability, logic, number theory and probability.
This clearly written, mathematically rigorous text includes a novel algorithmic exposition of the simplex method and also discusses the Soviet ellipsoid algorithm for linear programming; efficient algorithms for network flow, matching, spanning trees, and matroids; the theory of NP-complete problems; approximation algorithms, local search heuristics for NP-complete problems, more. All chapters are supplemented by thought-provoking problems. A useful work for graduate-level students with backgrounds in computer science, operations research, and electrical engineering. "Mathematicians wishing a self-contained introduction need look no further." — American Mathematical Monthly.
Our hero is Turing, an interactive tutoring program and namesake (or virtual emanation?) of Alan Turing, World War II code breaker and father of computer science. In this unusual novel, Turing's idiosyncratic version of intellectual history from a computational point of view unfolds in tandem with the story of a love affair involving Ethel, a successful computer executive, Alexandros, a melancholy archaeologist, and Ian, a charismatic hacker. After Ethel (who shares her first name with Alan Turing's mother) abandons Alexandros following a sundrenched idyll on Corfu, Turing appears on Alexandros's computer screen to unfurl a tutorial on the history of ideas. He begins with the philosopher-mathematicians of ancient Greece -- "discourse, dialogue, argument, proof...can only thrive in an egalitarian society" -- and the Arab scholar in ninth-century Baghdad who invented algorithms; he moves on to many other topics, including cryptography and artificial intelligence, even economics and developmental biology. (These lessons are later critiqued amusingly and developed further in postings by a fictional newsgroup in the book's afterword.) As Turing's lectures progress, the lives of Alexandros, Ethel, and Ian converge in dramatic fashion, and the story takes us from Corfu to Hong Kong, from Athens to San Francisco -- and of course to the Internet, the disruptive technological and social force that emerges as the main locale and protagonist of the novel.

Alternately pedagogical and romantic, Turing (A Novel about Computation) should appeal both to students and professionals who want a clear and entertaining account of the development of computation and to the general reader who enjoys novels of ideas.
Lewis and Papadimitriou present this long awaited Second Edition of their best-selling theory of computation. The authors are well-known for their clear presentation that makes the material accessible to a a broad audience and requires no special previous mathematical experience. In this new edition, the authors incorporate a somewhat more informal, friendly writing style to present both classical and contemporary theories of computation. Algorithms, complexity analysis, and algorithmic ideas are introduced informally in Chapter 1, and are pursued throughout the book. Each section is followed by problems.
This volume contains the papers presented at the International Workshop on Internet and Network Economics held during December 17-20, 2008, in Sha- hai, China, for its fourth edition. WINE 2008 provided a forum for researchers from di?erent disciplines to communicate with each other and exchange their researching ?ndings in this emerging ?eld. WINE 2008hadteninvitedspeakers: FanChungGraham, MatthewJackson, Lawrence Lau, Tom Luo, Eric Maskin, Paul Milgrom, Christos Papadimitriou, Herbert Scarf, Hal Varian and Yinyu Ye. There were 126 submissions. Each submission was reviewed on average by 2. 5 Programme Committee members. The Committee decided to accept 68 papers. The programme also included 10 invited talks. This ?nal program contained papers covering topics including equilibrium, information markets, sponsored auction, network economics, mechanism - sign, socialnetworks, advertisementpricing, computationalequilibrium, network games, algorithms and complexity for games. December 2008 Christos Papadimitriou Shuzhong Zhang Organization Programme Chairs Conference Chair Herbert E. Scarf (Yale University) Program Co-chair Christos Papadimitriou (UC Berkeley) Program Co-chair Shuzhong Zhang (Chinese University of Hong Kong) Local Organizing Committee Chairs Committee Chair Yifan Xu (Fudan University) Committee Co-chair Duan Li (Chinese University of Hong Kong) Committee Co-chair ShouyangWang(ChineseAcademyofSciences) Committee Co-chair Xiaoping Zhao (SSE INFONET Ltd.
An innovative, dramatic graphic novel about the treacherous pursuit of the foundations of mathematics.
This graphic novel recounts the spiritual odyssey of philosopher Bertrand Russell. In his agonized search for absolute truth, he crosses paths with thinkers like Gottlob Frege, David Hilbert & Kurt Gödel, & finds a passionate student in Ludwig Wittgenstein. But his most ambitious goal—to establish unshakable logical foundations of mathematics—continues to loom before him. Thru love & hate, peace & war, he persists in the mission threatening to claim both his career & happiness, finally driving him to the brink of insanity.
This story is at the same time a historical novel & an accessible explication of some of the biggest ideas of mathematics & modern philosophy. With rich characterizations & atmospheric artwork, it spins the pursuit of such ideas into a satisfying tale.
 Probing, layered, the book throws light on Russell’s inner struggles while setting them in the context of the timeless questions he tried to answer. At its heart, Logicomix is a story about the conflict between ideal rationality & the flawed fabric of reality.
This volume commemorates the life, work, and foundational views of Kurt G�del (1906-1978), most famous for his hallmark works on the completeness of first-order logic, the incompleteness of number theory, and the consistency - with the other widely accepted axioms of set theory - of the axiom of choice and of the generalized continuum hypothesis. It explores current research, advances, and ideas for future directions not only in the foundations of mathematics and logic, but also in the fields of computer science, artificial intelligence, physics, cosmology, philosophy, theology, and the history of science. The discussion is supplemented by personal reflections from several scholars who knew G�del personally, providing some interesting insights into his life. By putting his ideas and life's work into the context of current thinking and perceptions, this book will extend the impact of G�del's fundamental work in mathematics, logic, philosophy, and other disciplines for future generations of researchers.
"Ήτανε η καλύτερη εποχή, ήτανε η χειρότερη εποχή..." -οι καιροί μάς παραπέμπουν κατευθείαν στην περίφημη αρχή του μυθιστορήματος του Ντίκενς. Η επιστήμη θριαμβεύει και η τεχνολογία καλπάζει - αλλά οι πόλεμοι μαίνονται, η πλειοψηφία των συνανθρώπων μας πεινάει και μας κυβερνούν ανάξια ανδρείκελα. Ο Χρίστος Παπαδημητρίου, κορυφαίος επιστήμονας της Πληροφορικής, καθηγητής στο Μπέρκλεϊ, αλλά και συγγραφέας του μυθιστορήματος "Τούρινγκ: Μαθήματα αγάπης", μας μιλάει δίχως φραγμούς για τον κόσμο αυτό, τα λέει έξω από τα δόντια και δεν χαρίζεται σε κανέναν (με μοναδική ίσως εξαίρεση τους χάκερ του τίτλου). Το βιβλίο "Ισόβια στους χάκερ;" έχει άποψη για την τρομοκρατία και τη δημοκρατία, το Ίντερνετ και τα ναρκωτικά, τον πόλεμο και το κράτος, για την πνευματική ιδιοκτησία και την ιστορία των ιδεών, για τα γονίδια και τη θεωρία των παιγνίων. Μια άποψη πότε τεχνοκρατική και πότε ανατρεπτική, πολύ συχνά και τα δύο - και προπαντός μια άποψη πάντα τολμηρή, έξυπνη και φρέσκια.