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.

books

NEW! INDEPENDENCE a novel, 2017

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 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, 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 Ανεξαρτησία (εκδ. Πατάκη, Νοε. 2012), see here (and click at the bottom of that document for reviews in the Greek press), and here and here for two interviews about it.

teaching

I am not teaching this semester.

office hours:

Monday and Thursday 5-6pm.

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

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

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.

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

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.

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

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.