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, networks, and game theory.

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; here is a preview
• I have also written a novel entitled Turing, published in 2003 by MIT Press, and a book of essays in Greek Isovia stous hacker?
• …and a graphic novel Logicomix, written with Apostolos Doxiadis and illustrated by Alecos Papadatos and Annie di Donna. It has already appeared in Greek, soon in English (by Bloomsbury UK and USA), Italian, Japanese, Hebrew, and Dutch. (Btw, related to these last entries, here is a talk I gave on the relationship between story-telling and programming.)

teaching

In the Fall of 2009 I am teaching CS170.

Important notes:

If you were dropped from the waiting list, don’t despair yet, we are trying hard to admit you. Meanwhile, here is the second homework.

If you are in the class and you have decided to drop it, please do so now, many of your friends are waiting for your slot.

office hours:

Monday and Thursday 5-6pm.

ombudsman

I am the Computer Science Division’s ombudsman

other

I am a great fan of  Rachel Corrie.

And I support the Electronic Frontier Foundation

some recent publications:

computing equilibria

• 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 for anonymous games, with Costis Daskalakis. The idea is to siscretize 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.
• Three papers on the complexity of finding mixed Nash equilibria:  Reductions between graphical and normal form games, and   PPAD-completeness for 4-player normalform games, and three players too.
• 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.

algorithmic game theory

• 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?
• 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.
• A  tutorial on "Game Theory and Math Economics:  A TCS Introduction" that I presented at the 2001 FOCS.
• 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.

biology

• 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.
• 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.

complexity

• 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.
• The complexity of minimum distortion embeddings between point sets, with Muli Safra.  The distortion of bijections between two 3-dimensional point sets is hard to approximate within a factor better than 3.  (In the reduction, ignore the assumption, never  used, that the graph is cubic -- such graphs 3-coloring is easy, thanks to Andre Schulz for pointing this out to us.)

algorithms

• 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)ⁿ algorithm for k-SAT based on local search

multiobjective optimization

• 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).

internet and sensornets

• 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.
• Global synchronization in sensornets, with Richard Karp, Jeremy Elson, and Scott Shenker.
• On a conjecture related to greedy routing (with David Ratajczak) every planar 3-connected graph can be embedded on the plane so that greedy routing works.

computing equilibria

• 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.
• Three papers on the complexity of finding mixed Nash equilibria:  Reductions between graphical and normal form games, and   PPAD-completeness for 4-player normalform games, and three players too.
• 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.

database theory

• 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

general

• 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 MythematiCS: 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.

and some older papers

• W. Gates and C. Papadimitriou, Bounds for sorting by prefix reversal (1976)
• L. Kirousis and C. Papadimitriou, Complexity of recognizing polyhedral scenes (1985)
• C. Papadimitriou The Complexity of the Parity Argument and Other Inefficient proofs of Existence (1991)