CHRISTOS H. PAPADIMITRIOU

Visiting Professor AIT

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 UC San Diego.
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, 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)

and a novel entitled Turing (published recently in Greek as Turing's smile).

I taught (spring 2001): CS294 (section 1): Algorithms, Game Theory, and the Internet

SOME RECENT PUBLICATIONS

• 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).
• 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).
• E. Koutsoupias, C. H. Papadimitriou ``Beyond competitive analysis,'' proposes new ways of analyzing on-line algorithms. Preliminary version appeared in FOCS 94.
• 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.
• 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.
• 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.
• 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.
• 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 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.
• T. Kameda, Deng X., C. H. Papadimitriou ``How to learn an unknown environment,'' recent version of a FOCS 90 paper, to appear in JACM.
• C. H. Papadimitriou, M. Yannakakis ``On the complexity of database queries,'' Proceedings of the 1997 PODS, full version in JCSS.
• C. H. Papadimitriou, J. Tsitsiklis ``The complexity of optimum queuing network control,'' a natural optimization problem proved EXP-complete. To appear in Math. OR.
• D. Goldman, S. Istrail, C. H. Papadimitriou "Algorithmic aspects of protein structure similarity." Algorithms for matching and decomposing contact map graphs of proteins, a useful concept of similarity.
• P. Crescenzi, X. Deng, C. H. Papadimitriou ``On approximating a scheduling problem'' Approximation algorithms and non-approximability results for a scheduling problem modeling the communication phase of parallel computation.
• 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.
• M. Mihail, C. H. Papadimitriou ``On the random walk method for protocol testing,'' appeared in CAV 95.
• E. Koutsoupias, C. H. Papadimitriou ``Worst-case equilibria,''STACS 99. What is the price of anarchy in Internet routing?
• 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 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.
• 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.
• 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?"
• 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.
• E. Dantsin et al. A deterministic (2k/k+1)^n algorithm for k-SAT based on local search
• 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 the economics of information). 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 Algorithms, Games, and the Internet STOC 2001 (extended abstract in ICALP 2001). A survey of algorithmic problems related to Game Theory and the Internet.
• 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.
• A tutorial on "Game Theory and Math Economics: A TCS Introduction" that I presented at the 2001 FOCS.
• 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...)
• 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, Santosh Vempala On the Approximability of the Traveling Salesman Problem Our latest lower bounds for approximation ratios for the TSP (220/119, 117/117 for the symmetric case). Corrected results differ (one is slightly better, the other slightly worse) from those in the extended abstract in STOC 2000.
• 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)
• R. M. Karp, C. H. Papadimitriou, S. Shenker A Simple Algorithm for Finding Frequent Elements in Streams and Bags