*Christos H. Papadimitriou *

C. Lester Hogan Professor of EECS

Computer Science Division

University of California at Berkeley

Soda Hall 689

EECS Department

Berkeley, CA 94720, U.S.A.

(510) 642-1559

christos@cs,berkeley,edu

**I studied **in Athens Polytechnic (BS in EE 1972) and Princeton
(MS in EE, 1974 and PhD in EECS, 1976).

Since then, **I have taught **at Harvard,
MIT, Athens Polytechnic, Stanford, and UCSD.

**I came to Berkeley** in January 1996 (but I was here also in 1978 as a
Miller fellow).

**I am interested **in the theory of algorithms and complexity, and its
applications to databases, optimization, AI, the Internet, game theory, and
evolution.

**I am a member** of the National Academy of Sciences, the American
Academy of Arts and Sciences, and the National Academy of Engineering.

**I have written these books **

·
*Elements of the theory of computation *(Prentice-Hall 1982, with Harry
Lewis, *second edition September 1997 )* Click here for
typos in the second edition, here for postscript.

·
*Combinatorial* *optimization: algorithms and
complexity *(Prentice-Hall 1982, with Ken Steiglitz; second
edition by Dover, 1998)

·
*The* *theory of database concurrency control *(CS
Press 1988)

·
*Computational Complexity *(Addison Wesley, 1994)

· ** Algorithms** with Sanjoy
Dasgupta and Umesh Vazirani, McGraw-Hill 2006. Note: until recently, we had here the pdf of an early version of this book, for the convenience
of the students. Unfortunately, our
publisher demanded that we delete it. Advice to
authors: (a) make sure you keep the
copyright, and (b) do not publish with McGraw Hill.

·
I have also written a novel entitled ** Turing**, published in 2003 by MIT Press,
and a book of essays in Greek

· …*and**a graphic novel*** Logicomix**, written with Apostolos
Doxiadis and illustrated by Alecos
Papadatos and Annie di Donna. It has already appeared in Greek,
Dutch, English (by Bloomsbury UK and USA), and more than two dozen other
languages. (Btw, related to these last entries, here is a talk I gave on
the relationship between story-telling and
programming.)

...and the novel ** Independence** translated by Nina Bouri to Greek as

**I am a member**
of the National Academy of Sciences, the American Academy of Arts and Sciences,
and the National Academy of Engineering.

In Spring 2014 I'll be teaching a CS294
seminar on "Reading
the classics."

Plus a reading course on “Evolution and computation,” in conjunction with the semester at Simons Institute

Monday and Thursday 5-6pm.

I am the Computer Science Division’s *ombudsman*

**other**

I am a great fan of Rachel Corrie.

And I support the Electronic Frontier Foundation

And if you are interested in Greek politics
(and fluent in Greek…), here are my thoughts
about the crisis.

2012 was the year of Alan Turing's centenary!
Here is a piece I wrote.

**some**** publications**:

· Computing a Nash equilibrium is PPAD-complete, with Costis Daskalakis and Paul Goldberg, to appear in SIAM J. on Computing. And here is a paper on this that we recently wrote for CACM.

· A PTAS for Nash equilibria in anonymous games with Costis Daskalakis. The idea is to discretize the probabilities. This is for games with two strategies, in a later paper we handle any finite number of strategies per player.

· On the complexity of pure equilibria, with Alex Fabrikant and Kunal Talwar, explores the complexity of finding pure Nash equilibria in congestion games and similar games, pointing out that many of these problems are PLS-complete (that is, as hard to find as any object whose existence is guranteed by a potential function argument). A polynomial algorithm for the symmetric case leads to efficient combinatorial algorithms for computing Nash equilibria in non-atomic congestion games.

· Computing equilibria in multiplayer games with Tim Roughgarden. Algorithmic results for the special case of symmetric and other succinctly representable games: correlated equilibria can be found in polynomial time for a broad class that includes all previously known cases..

· Computing correlated equilibria in multiplayer games. correlated equilibria (a well-studied generalization of the Nash equilibrium due to Aumann) can be computed in polynomial time in essentially all kinds of multiplayer games studied in the literature: congestion, graphic, symmetric, local effect, facility location, scheduling, etc.

· The complexity of games on highly regular graphs (with Costas Daskalakis) finding a pure equilibrium on a game played on a d-dimensional grid is NEXP-complete, unless d = 1, in which case it is in P.

· Deng Xiaotie, C. H. Papadimitriou, Muli Safra On the Complexity of Equilibria., STOC 02 Approximability and communication complexity results related to price equilibrium computations when the goods are indivisible.

· C. H. Papadimitriou Algorithms, Games, and the Internet presented at *STOC/ICALP 2001*.
A survey of algorithmic problems related to Game Theory and the Internet.

· E. Koutsoupias, C. H. Papadimitriou ``Worst-case
equilibria,'' *STACS 99*. What
is the price of anarchy in Internet routing? Computing equilibria
in multiplayer games

· A complexity lower bound for a mechanism design problem, with Yaron Singer and Michael Schapira.

· .Revisiting the price of anarchy in selfish routing: What if the routers are selfish, not the flows? With Greg Valiant. The price of anarchy becomes unbounded. But in a model in which routers charge prices, the price of anarchy is one, that is, prices achieve the social optimum in routing.

· J. Feigenbaum, C. H. Papadimitriou, S. Shenker
Sharing the cost of multicast transactions *STOC
2000*. A problem in the interface between networking,
economics, and complexity, where insights in the efficiency (or lack thereof) in
distributed computation affect the landscape of possible solutions in the
problem of pricing multicasts.

· J. Feigenbaum, C. H. Papadimitriou, R. Sami, S. Shenker A BGP-based Mechanism for Lowest-cost Routing The Vickrey (or VCG) mechanism can be implemented without considerable overhead for Internet routing; initial experiments show that overpayments would be rather small (PODC 2002).

· Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H. Papadimitriou, Scott Shenker On a Network Creation Game, PODC 2003. The power of anarchy when nodes contribute costly links and are mindful of distances to other nodes.

· A mixability
theory of sex in evolution, with Adi Livnat, Jonathan Dushoff, and
Marcus Feldman, PNAS, December 2008. There had been no satisfactory
explanation of the advantages of sex in evolution, and yet sex is almost
ubiquitous among species despite its huge costs. Here we propose a
novel explanation: Using standard models, we establish that, rather
astonishingly, evolution of sexual species does *not* result in
maximization of fitness, but in improvement of another important measure which
we call ** mixability**: The ability
of a genetic variant to function adequately in the presence of a wide variety
of genetic partners.

· In a follow-up article we also point out that mixability lies at the root of modularity and the genetic hierarchy (without it there are no genes, families of genes, etc.)

· C. H. Papadimitriou and M. Sideri On the evolution of easy instances , reports experiments in which the genetic algorithm creates easy instances of the TSP. A possible connection to proteins is discussed.

· P. Crescenzi,
D. Goldman, C. H. Papadimitriou, A. Piccolboni, M. Yannakakis ``On the complexity of protein
folding'' NP-completeness of the two-dimensional H-P model. Preliminary
version appeared in *STOC 98*, full version in *J. of Comp. Biology*.

· R. Desper
et al. Inferring tree models for oncogenesis from comparative genome hybridization data to
appear *J. of Computational Biology*. First in a series of papers
applying a specialized (and combinatorial) learning algorithm to the problem of
detecting the genetic mechanisms of cancer development.

· C. H. Papadimitriou, J. Tsitsiklis ``The
complexity of optimum queuing network control,'' a natural optimization
problem proved EXP-complete. To appear in *Math.*
*OR*.

· C. H. Papadimitriou, Santosh Vempala On the Approximability of the Traveling Salesman Problem Our latest lower bounds for approximation ratios for the TSP (220/219, 117/116 for the symmetric case). Corrected results differ (one is slightly better, the other slightly worse) from those in the extended abstract in STOC 2000.

· M. Grigni,
V. Mirelli, C. H. Papadimitriou, ``On
the Difficulty of Designing Good Classifiers,'' a surprisingly strong (and
simple to prove) lower bound on designing good linear classifiers. *SIAM J.
Comp*.

· Z. Chen, M. Grigni, C. H. Papadimitriou ``Planar map graphs,'' an interesting variant of planarity
motivated by topological reasoning on the plane. Preliminary version appeared
in *STOC 98*.

· E. Dantsin et al. A
deterministic (2k/k+1)^{n} algorithm for k-SAT
based on local search

· C. H. Papadimitriou, M. Yannakakis
The complexity of tradeoffs, and optimal access of
web sources *FOCS 2000*. A complexity-theoretic
treatment of multiobjective optimization.
Approximate Pareto curves of small size exist for all such problems, but can be
constructed efficiently only under certain subtle conditions. Also, an
application to database
query optimization , a paper in PODS 2001.

· C. H. Papadimitriou and E. Servan-Schreiber The origins of the deadline: Optimizing communication in organizations (presented at a workshop on Complexity in Economic Games in Aix-en-Provence, 1999, and will appear in an edited book on complexity in economics). In a model in which information must travel fast within an organization, but information transmission entails "interruption costs," familiar organizational behaviors such as weekly meetings, monthly reports, and periodic deadlines seem to emerge as optimal strategies

· C. H. Papadimitriou ``Computational aspects of organization theory'' a survey of work on this topic which I presented at the 1996 European Symposium on Algorithms in Barcelona, Spain (published by Springer LNCS).

· R. M. Karp, E. Koutsoupias, C. H. Papadimitriou, S. Shenker
Algorithmic problems in congestion control
*FOCS 2000*. "Of which problem is TCP/IP congestion
control the solution?"

· Alex Fabrikant, Elias Koutsoupias, C. H.Papadimitriou Heuristically Optimized Trade-offs A simple model explains the power laws in degree sequences in the Internet graph. Are powerlaws the manifestation of complex multicriterion optimization? See also for an explanation of the mysterious power law in the eigenvalues of the Internet graph (it is a corollary of the degree power law...)

· Geographic Routing without Location
Information with Ananth Rao,
Sylvia Ratnasamy, Scott
Shenker, and Ion Stoica, *MOBICOM
2003.*

· M. Mihail, C. H. Papadimitriou, A. Saberi On Certain Connectivity Properties of the Internet Topology, FOCS 2003: Sparse scale-free graphs have good expansion properties, and random sparse graphs have low VCG overpayment.

· J. M. Hellerstein,
E. Koutsoupias, C. H. Papadimitriou ``Towards a theory of indexability,'' the characterization problem of
database query workloads which can be indexed effectively. Preliminary version
appeared in *PODS 97*.

· C. H. Papadimitriou, M. Sideri ``On the Floyd-Warshall
algorithm for logic programs,'' shows that the Floyd-Warshall
algorithm is essentially unique, *J. of Logic Programming*.

· J. Kleinberg, C. H.
Papadimitriou, P. Raghavan Two papers
on a novel approach to data mining. Preliminary version of one appeared in *STOC
98*, the other in the *J. of Knowledge
Discovery and Datamining*.

· C. H. Papadimitriou, M. Yannakakis ``On
the complexity of database queries,'' *Proceedings of the 1997 PODS*,
full version in *JCSS*.

· C. H. Papadimitriou, P. Raghavan, H. Tamaki, S. Vempala ``Latent semantic indexing: A probabilistic analysis,''
analyzes an information retrieval technique related to principle components
analysis. Preliminary version appeared in *PODS 98*. Full version in the *JCSS* special issue.

· J. Kleinberg, C. H.
Papadimitriou, P. Raghavan On the value of private information
*TARK* 2001. Privacy concerns for on-line information give rise to
algorithmic problems related to the computation of an individual's fair royalty
for the use of private information

· R. M. Karp, C. H. Papadimitriou, S. Shenker A Simple Algorithm for Finding Frequent Elements in Streams and Bags

· C. H. Papadimitriou ``Database metatheory: asking the
big queries'' a look at database theory, and CS theory in general, from the
point of view of the philosophy/history of science (a one-time experiment), for
*PODS 95*; reprinted in *SIGACT News,,* Spring 1996.

· C. H. Papadimitriou ``Extroverted complexity theory'' a short survey and
apologia of work that applies complexity concepts, results, and techniques to
fields outside CS. Appeared in *SIGACT News,,* Spring 1997.

· C. H. Papadimitriou ``NP-completeness: A retrospective,'' appeared in *ICALP
97* (published by Springer LNCS).

· C. H. Papadimitriou *Myth*emati**CS**: In Praise of Storytelling in the
teaching of CS and Math *Inroads *(SIGCSE Bulletin), based in a talk that I gave at the
International conference on CS Education ITICSE July 2 2003,
in Thessaloniki, Greece.