CHRISTOS H - Columbia Engineering



CHRISTOS H. PAPADIMITRIOU

Address:

Columbia University

Computer Science Department

500 W. 120th Street

New York NY 10027

christos@columbia.edu

Degrees:

October 1972: Diploma in Electrical Engineering, National Technical University of Athens.

August 1976: Ph.D., Princeton University

Honorary:

November 1997: Sc.D. (honoris causa) ETH, Zürich.

July 2003: Ph.D. (honoris causa) Univ. of Macedonia

September 2004: Ph.D. (honoris causa) Univ. of Athens

March 2008: Ph.D. (honoris causa) Univ. of Cyprus

May 2010: Ph.D. (honoris causa) University of Patras

October 2012: Ph.D. (honoris causa) National Technical University of Athens

November 2013: Ph.D. (honoris causa) EPFL, Lausanne

July 2015: Ph.D. (honoris causa) Univ. de Paris, Dauphine

Professional Activities and distinctions:

Fellow of the American Academy of Arts and Sciences (since 2001), Member, National Academy of Engineering (2002), National Academy of Sciences (2009), ACM Fellow (2002), Knuth Prize (2002), Katayanagi Prize (2008), Game Theory Society’s Game Theory and Computer Science Prize (2008). ACM-EATCS 2012 Gödel prize. EATCS award 2015, IEEE von Neumann Medal 2016, ETH platinum-gold price for education in CS, 2016. Named commander of the order of the phoenix by the president of the Hellenic republic, 2015.

On the Editorial board of J.ACM (1983-1986), J. of Computer and Systems Sciences, Combinatorica (1992–2011), Journal of Computer Science and Technology (Beijing, China), Algorithmica , Information and Computation, Journal of AI Research , Fundamenta Informaticae, SIAM J. on Discrete Mathematics (1999-2003) , Annals of Mathematics and Artificial Intelligence, and Journal of AI Research (1997-2002). On the program committee of several international conferences. Chair of the Program Committee for the 1989 STOC, 1999 PODS, and 2017 ITCS. Chair of the organizing committee for the 12th ICALP (1985, Nafplion, Greece). Chair of the IEEE Computer Society's Technical Committee on the Mathematical Foundations of Computing (1986-89). Chair of the organizing committee, 2013 FOCS (Berkeley).

Positions held:

• July 2017 – The Donovan Family Professor of Computer Science, Columbia University.

• January 1996 – December 2017: C. Lester Hogan Professor of Electrical Engineering and Computer Sciences, University of California Berkeley. Associate Chair for Computer Science, 1999-2002.

• July 2012 – June 2015: Senior Scientist, Simons Institute for the Theory of Computing, UC Berkeley.

• January 1988--December 1995: Irwin Mark and Joan Klein Jacobs Professor of Computer Science and Engineering, University of California at San Diego.

• April 1983--1988: Professor of Computer Science and Operations Research, Stanford University.

• December 1981-- January 1988: Professor of Computer Science, National Technical University of Athens.

• February 1979--March 1984: Assistant Professor of Computer Science, Massachusetts Institute of Technology. Associate Professor, as of July 1981.

• September 1978--January 1979: Miller Fellow for Science, University of California at Berkeley.

• July 1976--August 1978: Gordon McKay Assistant Professor of Computer Science, Harvard University.

Research Grants:

Continued support from the National Science Foundation since 1976.

Past Ph.D. Students:

• Paris Kanellakis (M.I.T. 1980, Professor, Brown University; deceased 1994)

• Joe Mitchell (Stanford 1986, now Professor at SUNY Stonybrook)

• Estie Arkin (Stanford 1986, now Professor at SUNY Stonybrook)

• Ellen Silverberg (Stanford 1986, now at AT&T Bell Laboratories)

• George Papageorgiou (NTU Athens 1986, now with Intrasoft, Greece)

• Thanassis Hadzilacos (NTU Athens 1986, now Professor, Open University, Cyprus)

• Vladislav Rutenburg (Stanford, 1987)

• George Georgakopoulos (NTU Athens, 1988, now Assoc. Professor at the Univ. of Crete)

• Dimitris Kavvadias (NTU Athens, 1988, now Assoc. Professor at the Univ. of Patras)

• Alejandro Schaffer (Stanford, 1988, now with NIH)

• Steve Vavasis (Stanford, 1988, now Professor at Waterloo)

• Alan Murray (Stanford 1989, now with IDA)

• Deng Xiaotie (Stanford, 1989, now Professor at Beijing University, China)

• Elias Koutsoupias (UCSD, 1994, now Professor at Oxford).

• Goran Gogic (UCSD, 1995, now with Celera Genomics).

• John Byers (Berkeley, 1996, co-advised with Mike Luby, now Professor at Boston University)

• Edouard Servan-Schreiber, (Berkeley, 2002, now at Teradata)

• Deborah Goldberg (Berkeley Math, 2000)

• Chris Umans (Berkeley, 2000, now Professor at Caltech)

• Kamalika Chaudhuri (Berkeley 2007, co-advised with Satish Rao, now Assoc. Professor at UCSD)

• Ziv Bar-Yossef (Berkeley, 2002, now at Google Israel)

• Kunal Talwar (Berkeley 2004, now at Google)

• James R. Lee (Berkeley 2006, now Professor at the Univ. of Washington)

• Alex Fabrikant (Berkeley 2008, now at Google)

• Costis Daskalakis, (Berkeley 2008, now Professor at M.I.T.)

• Henry Lin (Berkeley 2010, now researcher at Philips)

• George Pierrakos (2012, now at Goldman Sachs)

• Chris Wilkens (2012, now at Facebook Research)

• Greg Valiant (Berkeley 2013, now teaching at Stanford)

• Yaron Singer (2012, now teaching at Harvard)

• Raf Frongillo (2013, now teaching at Univ. of Colorado, Boulder)

• Aviad Rubinstein (2017, now Assistant Prof at Stanford)

• Alexandros Psomas (2017, now postdoc at CMU)

• Sam Wong (2018, now at Microsoft Research)

Currently advising: Frank Ban (UC Berkeley Math, co-advised with Luca Trevisan), Dan Mitropolsky (Columbia CS, co-advised with Michael Collins)

Postdocs mentored (selected): Sandi Irani, Toni Pitassi, Mic Grigni, Yair Bartal, Amir Ronen, Tim Roughgarden, Irit Dinur, Santosh Vempala, Moshe Babaioff, Bobby Kleinberg, Paul Valiant, Cai Yang, Vassilis Gkatzelis.

Has taught undergraduate and graduate courses on Algorithms and Complexity, Combinatorics, Combinatorial Algorithms, Theory of Computation, Introductory Programming, Compilers, Operating Systems, Databases, Complexity Theory, Combinatorial Optimization, Artificial Intelligence, Operations Research, Evolution, and Computation and the Brain.

University Service (selected)

Associate chair, UCSD Computer Science and Engineering Dept. (1988-91, 1994-96)

Member, UCSD CAP (1991-94)

Chair, Computer Science Division of EECS (1999-2002)

Member, Academic Advisory Committee for the Berkeley Art Museum/ Pacific Film Archive (2004-2010)

PUBLICATIONS OF CHRISTOS H. PAPADIMITRIOU

Books

1. H.R. Lewis, C. H. Papadimitriou Elements of the Theory of Computation, Prentice-Hall, 1981. Second Edition, 1998.

2. C. H. Papadimitriou, K. Steiglitz Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982. Second edition, Dover, 1998.

3. C. H. Papadimitriou The Theory of Database Concurrency Control, Computer Science Press, 1986.

4. C. H. Papadimitriou Computational Complexity, Addison-Wesley, 1993.

5. S. Dasgupta, U. Vazirani, C. H. Papadimitriou, Algorithms, McGraw-Hill, 2006.

6. (Edited) M. Baaz, C. Papadimitriou, H. Putnam, D. Scott, C. Harper (editors.) Kurt Gödel and the Foundations of Mathematics, Cambridge University Press, 2011.

Fiction and essays

7. C.H. Papadimitriou, Turing: A Novel about Computation MIT Press 2003. Published in Greek as Turing’s Smile, 2001, translated to Portuguese.

8. C.H. Papadimitriou, “Ισόβια στους χάκερ;” (“Life-sentence to hackers?”) essays in Greek, May 2004.

9. A. Doxiadis, C. H. Papadimitriou, Logicomix, Bloomsbury 2009 (translated in 25 languages, 14 weeks on the New York Times best seller list.)

10. C. H. Papadimitriou Independence, Pataki publishers November 2012 (in Greek); Amazon (English).

Chapters in books

1. D.S. Johnson, C. H. Papadimitriou, “Computational Complexity,” in The Traveling Salesman Problem, E.L. Lawler, J.K. Lenstra, A.G. Rinooy Kan (Eds.), J. Wiley and Sons, 1985.

2. D.S. Johnson, C. H. Papadimitriou, “Worst-Case Analysis of Heuristics,” in The Traveling Salesman Problem, E.L. Lawler, J.K. Lenstra, A.G. Rinooy Kan (Eds.), J. Wiley and Sons, 1985.

3. C. H. Papadimitriou, “Computational Complexity: An Annotated Bibliography”, in Combinatorial Optimization , edited by E.L. Lawler, J.K. Lenstra, M. O'hEigherdaigh, A.G. Rinooy Kan, 1985.

Journal articles

1. C. H. Papadimitriou, “The NP-completeness of the Bandwidth Minimization Problem,” Computing, 16, pp. 263-270, 1976.

2. C. H. Papadimitriou, “On the Complexity of Edge Traversing,” J.ACM, 23, pp. 544-554, 1976.

3. C. H. Papadimitriou, K. Steiglitz, “The Complexity of Local Search for the Traveling

Salesman Problem,” SIAM J. on Computing 6, pp. 76-83, 1977.

4. C. H. Papadimitriou, “The Algebraic Complexity of Certain Sets of Functions,” Bulletin of the Greek Mathematical Society, 17, 1, 1977.

5. C. H. Papadimitriou “The Euclidean Traveling Salesman Problem is NP-complete,” Theoretical Computer Science, 4, 3, pp. 237-244, 1977.

6. C. H. Papadimitriou, “The Adjacency Relation on the Traveling Salesman Polytope is NP-complete,” Math. Programming, 14, pp. 312-324, 1978.

7. C. H. Papadimitriou, K. Steiglitz, “Some Examples of Difficult Traveling Salesman Problems,” Operations Research, 26, 3, pp. 434-443, 1978.

8. C. H. Papadimitriou, “The Complexity of the Capacitated Tree Problem,” Networks, 8, 3, pp. 217-230, 1978.

9. P.A. Bernstein, N. Goodman, J.B. Rothnie, C. H. Papadimitriou, “Analysis of Serializability of SDD-1: A System of Distributed Databases,” IEEE Transactions on Software Engineering, SE-4, 3, pp. 154-168, 1978.

10. H.R. Lewis, C. H. Papadimitriou, “The Complexity of Algorithms,” Scientific American, 238, 1, January 1978.

11. C. H. Papadimitriou, “On the Optimality of the Fast Fourier Transform,” J.ACM, 26, 1, pp. 95- 102,1979.

12. C. H. Papadimitriou, M. Yannakakis, “Scheduling Interval-Ordered Tasks,” SIAM J. Computing, 8, 3, pp. 405-409, 1979.

13. C. H. Papadimitriou, “Efficient Search for Rationals,” Information Processing Letters, 8, 1, pp. 1-4, 1979.

14. C. H. Papadimitriou, “The Serializability of Concurrent Database Updates,” J.ACM, 26, 4, pp. 631-653, 1979.

15. W. Gates, C. H. Papadimitriou, “Bounds for Sorting by Prefix Reversal,” Discrete Mathematics 27 , 1, pp. 47-58, 1979.

16. C. H. Papadimitriou, P.C. Kanellakis, “Flowshop Scheduling with Limited Temporary Storage,” J.ACM, 27, 3, pp. 533-549, 1980.

17. C. H. Papadimitriou, P.A. Bernstein, “The Performance of Balanced Hashing Functions when the Keys are not Equiprobable,” ACM Trans. on Progr. Languages and Systems, 2, 1, pp. 77-89, 1980.

18. M.R. Garey, D.S. Johnson, M.L. Miller, C. H. Papadimitriou, “The Complexity of Coloring Circular Arcs and Chords,” SIAM J. Discrete and Algebraic Methods, 1, 2, 1980.

19. P.C. Kanellakis, C. H. Papadimitriou, “Local Search for the Asymmetric Traveling Salesman Problem,” Operations Research, 28 , 5, pp. 1086-1099, 1980.

20. C. H. Papadimitriou, M. Yannakakis, “The Complexity of Restricted Spanning

Tree Problems,” J.ACM, 29, 2, pp. 285-309, 1982.

21. A. Itai, R.J. Lipton, C. H. Papadimitriou, M. Rodeh, “Covering Graphs with Cycles,” SIAM J. Computing, 10 , 4, pp. 746-750, 1981.

22. C. H. Papadimitriou, “Worst-Case and Probabilistic Analysis of a Geometric Location Problem,” SIAM J. Computing, 10 , 3, pp. 542-557, 1981.

23. W. Lipski, C. H. Papadimitriou, “A Fast Algorithm for Testing for Correctness and Detecting Deadlocks in Locked Transaction Systems,” J. of Algorithms, 2, pp. 211-226, 1981.

24. A. Itai, C. H. Papadimitriou, J. Swarcfiter, “Hamilton Paths in Grid Graphs,” SIAM J. Computing, 10 , 4, pp. 676-686, 1981.

25. H.R. Lewis, C. H. Papadimitriou, “Symmetric Space-Bounded Computation,” Theoretical Computer Science, 19, 1, pp. 161-187, 1982.

26. C. H. Papadimitriou, “On the Complexity of Integer Programming,” J.ACM, 28, 2, pp. 765-769, 1981.

27. C. H. Papadimitriou, D.E. Knuth, “Duality in Addition Chains”, Bulletin of the EATCS, February 1981.

28. C. H. Papadimitriou, M. Yannakakis, “The Clique Problem in Planar Graphs,” Information Processing Letters 13, 4-5, pp. 131-133, 1981.

29. C. H. Papadimitriou, M. Yannakakis, “On Minimal Eulerian Graphs,” Information Processing Letters 12, 4, pp. 202-205, 1981.

30. M. Blum, R.M. Karp, C. H. Papadimitriou, O. Vornberger, M. Yannakakis, “Testing whether a Graph is a Superconcentrator is coNP-complete,” Information Processing Letters 13 , 4-5, pp. 164-167, 1981.

31. C. H. Papadimitriou, “On the Symbolic Evaluation of Determinants,” Bulletin of the Greek Mathematical Society, 22, 1, 1982.

32. R.M. Karp, C. H. Papadimitriou, “On Linear Characterizations of Combinatorial Optimization Problems,” SIAM J. Computing 11, 4, pp. 620-632, 1982.

33. M. Yannakakis, C. H. Papadimitriou, “Algebraic Dependencies,”J.CSS 25 (special issue for the 22nd FOCS Conference), 1, pp. 2-42, 1982.

34. C. H. Papadimitriou, “A Theorem in Database Concurrency Control”, J.ACM, 29, 4, pp. 998-1006, 1982.

35. C. H. Papadimitriou, “Concurrency Control by Locking”, SIAM J. Computing 12, 2, pp. 215-226, 1983.

36. A. La Paugh, C. H. Papadimitriou, “The Even Path Problem for Graphs and Digraphs,” Networks, 14, 4, pp. 507-514, 1984.

37. S. Cosmadakis, C. H. Papadimitriou, “The Traveling Salesman Problem with Many Visits to Few Cities,” SIAM J. Computing, 13 , 1, pp. 99-109, 1984.

38. C. H. Papadimitriou, U. Vazirani, “On Two Geometric Problems Related to the Traveling Salesman Problem,” J. of Algorithms, 5 , 2, pp. 231-246, 1984.

39. P.C. Kanellakis, C. H. Papadimitriou, “Is Distributed Locking Harder?” J.CSS, 28, 1, 1984 (special issue for the 1982 PODS Conference).

40. M.A. Casanova, R. Fagin, C. H. Papadimitriou, “Inclusion Dependencies and their Relation to Functional Dependencies,” J.CSS, 28 , 1, pp. 29-59, 1984 (special issue for the 1982 PODS Conference).

41. P.C. Kanellakis, C. H. Papadimitriou, “The Complexity of Distributed Concurrency Control,” SIAM J. Computing, pp. 52-74, 1985.

42. E. Dahlhaus, D.S. Johnson, C. H. Papadimitriou, P. Seymour, M. Yannakakis, “The Complexity of Multiway Cuts,” SIAM J. Computing, 1997.

43. C. H. Papadimitriou, M. Yannakakis “The Complexity of Facets (and Some Facets of Complexity),” J.CSS, 28 , 2, pp. 244-259, 1984 (special issue for the 1982 STOC Conference).

44. C. H. Papadimitriou, M. Sipser, “Communication Complexity,” J.CSS, 28, pp. 260-269, 1984 (special issue for the 1982 STOC Conference).

45. C. H. Papadimitriou, J. Tsitsiklis “On the Complexity of Designing Distributed Protocols,” Information and Control 53, 3, pp. 211-218, 1983.

46. H.T. Kung, C. H. Papadimitriou, “An Optimality Theory of Database Concurrency Control,” Acta Informatica 19, 1, pp. 1-13, 1984.

47. F. Afrati, S. Cosmadakis, N. Papaconstantinou, G. Papageorgiou, C. H. Papadimitriou “The Traveling Repairman Problem,” R.A.I.R.O, Informatique Theorique, 1985.

48. C. H. Papadimitriou, P.C. Kanellakis, “On Concurrency Control Using Multiple Versions,” ACM T.ODS, 9 , 1, pp. 89-99, 1984.

49. N. Megiddo, S. Hakimi, M.R. Garey, D.S. Johnson, C. H. Papadimitriou, “The Complexity of Searching a Graph,” JACM , 1988.

50. C. H. Papadimitriou,“On the Complexity of Unique Solutions,” J.ACM 31, 1, pp. 392-400, 1984.

51. S. Cosmadakis, C. H. Papadimitriou, “Updating Relational Views,” J.ACM 31, 4, pp. 742-760, 1984.

52. F. Makedon, C. H. Papadimitriou, I.H. Sudborough, “Topological Bandwidth,” SIAM J. Discrete and Algebraic Methods, 1984.

53. L. Kirousis, C. H. Papadimitriou, “Pebbling and Searching,” Theoretical Computer Science, 1986.

54. L. Kirousis, C. H. Papadimitriou, “Interval Graphs and Searching,” Discrete Mathematics, 55, pp. 181-184, 1985.

55. F. Afrati, C. H. Papadimitriou, G. Papageorgiou, “The Complexity of Cubical Graphs,” Information and Control, 1985.

56. C. H. Papadimitriou, “Games Against Nature,” J.CSS, 31 (special issue for the 1983 STOC Conference), 2, pp. 288-301, 1985.

57. C. H. Papadimitriou, J. Tsitsiklis, “A Simple Criterion for Structurally Fixed Modes,” Systems and Control Letters, 4, pp. 333-337, 1984.

58. E. Arkin, C. H. Papadimitriou, “The Complexity of Circulations,” J. of Algorithms, 1986.

59. C. H. Papadimitriou, J. Tsitsiklis, “The Performance of a Precedence-Based Queuing Discipline,” JACM, 33 , 3, pp. 593-602, 1986.

60. C. H. Papadimitriou, “An Algorithm for Shortest-Path Motion in Three Dimensions,” Information Processing Letters, 1985.

61. C. H. Papadimitriou, J.D. Ullman, “A Communication-Time Trade-off,” to SIAM J. Computing, 1988.

62. G. Georgakopoulos, C. H. Papadimitriou, “The 1-Steiner Tree Problem,” J. of Algorithms, 1987.

63. C. H. Papadimitriou, J. Tsitsiklis, “Intractable Problems in Control Theory,” SIAM J. Control and Optimization and Control, 24, pp. 639-654, 1986.

64. L. Kirousis, C. H. Papadimitriou, “The Complexity of Recognizing Polyhedral Scenes,” special issue of J.CSS for the 1985 FOCS Conference, 1988.

65. C. H. Papadimitriou, “The Largest Subdeterminant of a Matrix,” Bulletin of the Math. Society of Greece, 25, pp. 96-105, 1984.

66. E. Arkin, C. H. Papadimitriou, “Negative Cycles in Mixed Graphs,” Oper. Res. Letters , 1985.

67. C. H. Papadimitriou, J.N. Tsitsiklis, “On the Stochastic Scheduling with In-tree Precedence Constraints,” SIAM J. Computing, 16 pp. 1-6, 1987.

68. C. H. Papadimitriou, J.N. Tsitsiklis, “The Complexity of Markov Decision-Making,” Math. O.R. , 1988.

69. J. Mitchell, D. Mount, C. Papadimitriou, “The Discrete Geodesic Problem,” SIAM J. Computing, 18, 1987.

70. T. Hadzilacos, C. H. Papadimitriou, “Algorithmic Issues in Multiversion Concurrency Control,” J.CSS 1987 (special issue for the 1985 PODS Conference).

71. C. H. Papadimitriou, “A Note on the Expressive Power of PROLOG,” Bulletin of the EATCS, July 1985.

72. C. H. Papadimitriou, M. Yannakakis, “A Note on Succinct Encodings of Graphs,”

Information and Control 71, 3, pp. 181-185, 1987.

73. C. H. Papadimitriou, M. Yannakakis, “The Complexity of Reliable Concurrency Control,” SIAM J. Computing, 1987.

74. D.S. Johnson, C. H. Papadimitriou, M. Yannakakis, “How Easy is Local Search?” J.CSS, 1988 (special issue for the 1985 FOCS Conference).

75. C. H. Papadimitriou, D. Wolfe “The Complexity of Facets Resolved,” J.CSS, 1988 (special issue for the 1985 FOCS Conference).

76. D.S. Johnson, C. H. Papadimitriou, M. Yannakakis “On Generating All Maximal Independent Sets,'' Information Processing Letters, 1988.

77. C. H. Papadimitriou, E. Silverberg “Optimal Piecewise Linear Motion of an Object Among Polygonal Obstacles,'' Algorithmica, 1987.

78. F. Afrati, C. H. Papadimitriou, G. Papageorgiou, “The Synthesis of Communication Protocols,” Algorithmica, 1988.

79. S. Efremidis, C. H. Papadimitriou, M. Sideris,“Complexity Characterizations of Attribute Grammar Languages,” Information and Control, 1988.

80. E. Arkin, C. H. Papadimitriou, M. Yannakakis, “Modularity of Paths and Cycles,” J.ACM, 1990.

81. G. Georgakopoulos, D. Kavvadias, C. H. Papadimitriou,“Probabilistic Satisfiability,” J. of Complexity, 1988.

82. X. Markenscoff, C. H. Papadimitriou, “Optimal Prehension of Polygons,” International J. of Robotics Research, 1989.

83. X. Markenscoff, L. Ni, C. H. Papadimitriou, “The Geometry of Grasping,” International J. of Robotics Research, 1990.

84. J. Mitchell, C. Papadimitriou, “The Weighted Regions Problem,” J.ACM, 1990.

85. F. Afrati, C. H. Papadimitriou, G. Papageorgiou, A. Roussou, Y. Sagiv, J.D. Ullman, “On the Convergence of Sideways Information Passing,” J.CSS, 1989 (special issue for the 1986 PODS Conference).

86. C. H. Papadimitriou, E. Silverberg, “Restricted Motion of Two Points among Obstacles,'' J. of Algorithms, 1989.

87. F. Afrati, C. H. Papadimitriou, “The Parallel Complexity of Simple Logic Programs,” J.ACM, 40, 4, pp. 891--916, 1993.

88. D.E. Knuth, C. H. Papadimitriou, J.N. Tsitsiklis, “A Note on Strategy Elimination in Bimatrix Games,” Operations Research Letters, 1988.

89. C. H. Papadimitriou, M. Yannakakis, “Optimization, Approximation, and Complexity Classes,” special issue of J.CSS for the 1988 STOC Conference.

90. C. H. Papadimitriou, M. Yannakakis, “Towards an Architecture-Independent

Analysis of Parallel Algorithms,” SIAM J. on Computing , 1989.

91. C. H. Papadimitriou, M. Yannakakis, “On Recognizing Integer Polyhedra,” Combinatorica, 1991.

92. X. Deng, C. H. Papadimitriou, “On Path Lengths Modulo Three,” J. of Graph Theory, 1990.

93. Ph. Kolaitis, C. H. Papadimitriou, “Why Not Negation By Fixpoint?”, special issue of JCSS for the 1988 PODS, 1992.

94. Ph. Kolaitis, C. H. Papadimitriou, “Some Computational Aspects of Circumscription,” J.ACM , 1990.

95. J. Kollias, C. H. Papadimitriou,“Optimum Processing Sequence of Batched Queries,” Information Processing Letters, 1990.

96. C. H. Papadimitriou, M. Yannakakis, “The Traveling Salesman Problem with Distances 1 and 2,” Math. of Operations Research, 18, pp. 1-11, 1993.

97. D. Kavvadias, C.H Papadimitriou, “A Linear Programming Approach to Reasoning About Probabilities,” Annals of Mathematics and Artificial Intelligence, 1990.

98. M. D Hirsch, C. H. Papadimitriou, S. A. Vavasis, “Exponential Lower Bounds for Finding Brouwer Fixpoints,” J. of Complexity, 5, 379--416, 1989.

99. C. H. Papadimitriou, M. Yannakakis, “The Complexity of Reliability,” SIAM J. Computing , 1987.

100. X. Deng, C. H. Papadimitriou, “The Complexity of Solution Concepts,” Mathematics of Operations Research, 19, 2, pp. 257--266, 1994.

101. C. H. Papadimitriou, “On Games Played by Automata with a Bounded Number of States,” J. Games and Econ. Behavior, 4, 1, pp. 122-131, 1992.

102. C. H. Papadimitriou, M. Yannakakis, “Shortest Paths without a Map,'' special issue of Theor. Computer Science for the 1989 ICALP Conference, 1991.

103. C. H. Papadimitriou, M. Sideri, V. Rangan, “Synthesizing Communication Networks from Trust Specifications,'' Algorithmica, 11 5, pp. 485--499, 1994.

104. C. H. Papadimitriou, M. Sideri, “The Bisection Width of Grid Graphs,” Mathematical Systems Theory, 1996.

105. X. Deng, C. H. Papadimitriou, “Searching an Unknown Graph,”SIAM J. Computing.

106. S. Buss, C. H. Papadimitriou, J. N. Tsitsiklis, “On the Predictability of Coupled Finite Automata: An Allegory about Chaos,” J. of Complexity, 1992.

107. N. Megiddo, C. H. Papadimitriou, “On Total Functions, Existence Theorems, and Complexity,'' Theoretical Computer Science, 1991.

108. C. H. Papadimitriou, “The Complexity of the Lin-Kernighan Heuristic for the Traveling Salesman Problem,'' SIAM J. Computing, 21, pp. 450--465, 1992.

109. C. H. Papadimitriou, P. Serafini, M. Yannakakis, “The Communication Capacity of Reserved Lines,'' Applied Discrete Math., 42, pp. 271--278, 1993

110. C. H. Papadimitriou, “On the Complexity of the Parity Argument and other Inefficient Proofs of Existence,'' JCSS, 48 , 3, 498--532, 1994.

111. E. Koutsoupias, C. H. Papadimitriou, M. Sideri, “Optimal Bisection of a Polygon,'' ORSA J. on Computing, 4, pp. 345--348, 1992.

112. E. Koutsoupias, C. H. Papadimitriou, “On the Greedy Algorithm for Satisfiability,'' Information Processing Letters, 43, pp. 53--55, 1992.

113.C. H. Papadimitriou, M. Yannakakis “Tie--breaking Semantics and Structural Totality of Logic Programs,” invited to the special issue of J.CSS. for the 1992 PODS.

114. T. Kameda, X. Deng, C. H. Papadimitriou, “How to Learn an Unknown Environment I:

The Rectilinear Case,” JACM, 1998.

115. X. Deng, C. H. Papadimitriou, “Competitive Distributed Decision-Making and the Value of Information,” Algorithmica.

116. C. H. Papadimitriou, M. Sideri, “Default Theories That Always Have Extensions,'' Artificial Intelligence, 69 , 1--2, pp. 347--357, 1994.

117. C. H. Papadimitriou, M. Yannakakis “On Limited Nondeterminism and the Complexity of the Vapnic-Chervonenkis Dimension,'' invited to the special issue of J.CSS for Structures 1993.

118. C. H. Papadimitriou, J. N. Tsitsiklis “The Complexity of Queuing Networks Control,'' Math. of O. R., 2000.

119. E. Koutsoupias, C. H. Papadimitriou, “On the k-server Conjecture,'' J.ACM , 1995.

120. E. Koutsoupias, C. H. Papadimitriou,“The 2-evader Problem,'' IPL , 1995.

121. P. Crescenzi, C. H. Papadimitriou, “Reversible simulation of space-bounded computations,'' Theoretical Comp. Sci, 143 , 1, pp. 159--165, 1995.

122. C. H. Papadimitriou, S. Ramanathan, P. Venkat Rangan, S. Sampathkumar “Multimedia information caching for personalized video-on-demand,” Computer Communications, 18 , 3, pp. 204--216, 1995.

123. Y. Dimopoulos, V. Magirou, C. H. Papadimitriou, “On Kernels, Defaults, and Even Graphs,'' Annals of Math. and AI , 1997.

124. S. Abiteboul, C. H. Papadimitriou, V. Vianu “The Power of Reflective Relational Machines,'' J.CSS special issue on 1995 LICS.

125. C. H. Papadimitriou, M. Yannakakis “On the complexity of database queries,'' invited to the special issue of J.CSS for the 1997 PODS.

126. X. Deng, C. H. Papadimitriou, “Decision-making by hierarchies of discordant agents,'' Mathematical Programming, 86, 2, pp 417-431, 1999.

127. C. H. Papadimitriou, D. Suciu, V. Vianu, “Topological Queries in Spatial Databases,” JCSS, 58(1): 29-53, 1999.

128. E. Koutsoupias, C. H. Papadimitriou “Beyond Competitive Analysis,'' SIAM J. Computing, 2001.

129. G. Gogic, C. H. Papadimitriou, M. Sideri “Incremental Recompilation of Knowledge,'' J. of AI Research, 1997.

130 C. H. Papadimitriou, M. Sideri “On the Floyd-Warshall Algorithm for Logic Programs,” Journal of Logic Programming, 2001.

131 M. Grigni, V. Mirelli and C. H. Papadimitriou, “On the Difficulty of Designing Good Classifiers,” SIAM J. on Computing, 2001.

132 V. D. Blondel, O. Bournez, P. Koiran, C. H. Papadimitriou, J.N. Tsitsiklis, “Deciding Stability and Mortality of Piecewise Affine Dynamical Systems,” TCS 255(1-2): 687-696, 2001.

133 P. Crescenzi, X. Deng, C. H. Papadimitriou ``On approximating a scheduling problem'' Journal of Combinatorial Optimization, 5, 287-297, 2001.

134 C.H. Papadimitriou, P. Raghavan, H. Tamaki, S. Vempala. “Latent Semantic Indexing: A Probabilistic Analysis.” JCSS 61(2): 217-235, 2000.

135 R. Desper, F. Jiang, O.-P. Kallioniemi, H. Moch, C.H. Papadimitriou, A.A. Schaffer: “Inferring Tree Models for Oncogenesis from Comparative Genome Hybridization Data.” Journal of Computational Biology, 6(1): 37-52, 1999.

136 X.-T. Deng, C.H. Papadimitriou, “Decision-making by Hierarchies of Discordant Agents,” Math. Programming, 1999.

137 F. Jiang, R. Desper, C.H. Papadimitriou, A. Schaeffer, O. Kallioniemi, J. Richter, P. Schraml, G. Sauter, M. Mihatsch, H. Moch: “Construction of Evolutionary Tree Models for Renal Cell Carcinoma from Comparative Genome Hybridization Data,” Cancer Research 60, 6503-6509, 2000.

138 R. Simon et al, “Chromosme Abnormalities in Ovarian Adenocarcinoma III,” Genes, Chromosomes, and Cancer, 28: 106-120, 2000.

139 R. Desper, F. Jiang, O.-P. Kallioniemi, H. Moch, C.H. Papadimitriou, A.A. Schaffer, “Distance-Based Reconstruction of Tree Models for Oncogenesis,” Journal of Computational Biology, 7(6): 789-803, 2000.

140 E. Dantsin, A. Goerdt, E. A. Hirsch, R. Kannan, J. Kleinberg, C.H. Papadimitriou, P. Raghavan, U. Schöning, “A Deterministic (2-2/(k+1))n Algorithm for k-SAT Based on Local Search,” Theoretical Computer Science, 2001.

141 J. Feigenbaum, C.H. Papadimitriou, S. Shenker, “Sharing the Cost of Multicast Transmissions,” JCSS 63(1): 21-41, 2001.

142 V.D. Blondel, O. Bournez, P. Koiran, C.H. Papadimitriou, J.N. Tsitsiklis, Deciding Stability and Mortality of Piecewise Affine Dynamical Systems,” TCS 255(1-2): 687-696, 2001.

143 J. Hellerstein, E. Koutsoupias, C.H. Papadimitriou, V. Samoladas, “The Indexability of Database Workloads,” JACM 49(1): 35-55, 2002.

144 Z.-Z. Chen, M. Grigni, C.H. Papadimitriou, “Map Graphs,” JACM 49(2): 127-138, 2002.

145 X. Deng, C.H. Papadimitriou, S. Safra, “On the Complexity of Price Equilibria,” J. Comput. Syst. Sci. 67(2): 311-324, (2003) 2002.

146 J.M. Kleinberg, C.H. Papadimitriou, P. Raghavan, “Auditing Boolean Attributes,” J. Comput. Syst. Sci. 66(1): 244-253, 2003.

147 G. Gottlob, C.H. Papadimitriou, “On the Complexity of Single-Rule Datalog Queries,” Inf. Comput, 183(1): 104-122, 2003.

148 R.M. Karp, S. Shenker, C.H. Papadimitriou, “A Simple Algorithm for Finding Frequent Elements in Streams and Bags,” ACM Trans. Database Syst. 28, 51-55, 2003.

149 J.M. Kleinberg, C.H. Papadimitriou, P. Raghavan, “Segmentation Problems.” J. ACM 51(2): 263-280, 2004.

150 A. Archer, C.H. Papadimitriou, K. Talwar, É. Tardos, “An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents,” J. of Internet Math, 1, 2, 2004.

151 M. Mihail, C.H. Papadimitriou, A. Saberi, “On certain connectivity properties of the internet topology,” J. Comput. Syst. Sci. 72 (2): 239-251, 2006.

152 J. Feigenbaum, C.H. Papadimitriou, R. Sami, S. Shenker, “A BGP-based Mechanism for Lowest-Cost Routing,” Distributed Computing 18(1): 61-72, 2005.

153 C.H. Papadimitriou, D. Ratajczak, “On a Conjecture Related to Geometric Routing,” Theor. Comput. Sci. 344 (1): 3-14, 2005.

154. V. Koltun, C.H. Papadimitriou, “Approximately Dominating Representatives,” Theor. Comput. Sci. 371 (3): pp. 148-154, 2007.

155. C.H. Papadimitriou, T. Roughgarden, “Computing correlated equilibria in multi-player games,” JACM, 2008.

156. N.R. Devanur, C.H. Papadimitriou, A. Saberi, V.V. Vazirani “Market equilibrium via a primal-dual algorithm for a convex program,” JACM, 2008.

157. A. Livnat, C. Papadimitriou, J. Dushoff, M. Feldman, “A Mixability Theory for the Role of Sex in Evolution,” Proc. Of the National Academy of Sciences, 2008.

158. Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou: The Complexity of Computing a Nash Equilibrium. SIAM J. Comput. 39(1): 195-259 (2009)

159. Constantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou: A note on approximate Nash equilibria. Theor. Comput. Sci. 410(17): 1581-1588 (2009)

160. Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno: On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12-14): 1054-1065 (2011)

161 A. Livnat, C. Papadimitriou, N. Pippenger, M. Feldman, “Sex, Mixability, and Modularity,” Proc. Of the National Academy of Sciences, 2010.

162. Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou: The complexity of computing a Nash equilibrium. Commun. ACM 52(2): 89-97 (2009)

163. Elias Koutsoupias, Christos H. Papadimitriou: Worst-case equilibria. Computer Science Review 3(2): 65-69 (2009)

164. Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. SIAM J. Comput. 38(6): 2330-2355 (2009)

165. Anthony Spatharis, Ilias Foudalis, Martha Sideri, Christos H. Papadimitriou: Comparing Trade-off Based Models of the Internet. Fundam. Inform. 92(4): 363-372 (2009)

166. A Livnat, C. Papadimitriou, M. Feldman “An analytical contrast between fitness maximization and selection for mixability” Journal of Theoretical Biology, 2010.

167. Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou “The myth of the Folk Theorem” Games and Economic Behavior 70(1): 34-43 (2010)

168. Christos H. Papadimitriou “Alan and I,” Commun. ACM 55(9): 42-43 (2012)

169. Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani “The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions,” ACM Trans. Economics and Comput. 1(2): 9 (2013)

170. Erick Chastain, Adi Livnat, Christos Papadimitriou, Umesh Vazirani “Algorithms, Games, and Evolution”, PNAS 2014.

171. Constantinos Daskalakis, Christos H. Papadimitriou “Approximate Nash equilibria in anonymous games,” J. Economic Theory 156: 207-245 (2015)

172. Christos H. Papadimitriou “Algorithms, Complexity, and the Sciences”, PNAS (2014)

|173. A Livnat, C Papadimitriou, “Sex as an algorithm: the theory of evolution under the lens of computation” Communications of the ACM 59 | | |

|(11), 84-93 | | |

| | | |

|174. A Othman, C Papadimitriou, A Rubinstein, “The complexity of fairness through equilibrium,” ACM Transactions on Economics and | | |

|Computation (TEAC) 2016. | | |

175. Yang Cai, Ozan Candogan, Constantinos Daskalakis, Christos H. Papadimitriou:

Zero-Sum Polymatrix Games: A Generalization of Minmax. Math. Oper. Res. 41(2): 648-655 2016.

176. Christos H. Papadimitriou, Georgios Piliouras From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory. Entropy 20(10): 782 (2018).

177. Paul W. Goldberg, Christos H. Papadimitriou, Towards a unified complexity theory of total functions. J. Comput. Syst. Sci. 94: 167-192 (2018).

178. Christos H. Papadimitriou, Georgios Piliouras: Game dynamics as the meaning of the Game, SIGECOM Exchanges, June 2018, pp 53—63.

178. Liudmyla Vasylenko, Christos Papadimitriou, Marcus Feldman, Sex: the power of randomization, Theoretical Population Biology, 2019.

179. Frank Ban, Kamal Jain, Christos H. Papadimitriou, Christos-Alexandros Psomas, Aviad Rubinstein: Reductions in PPP. Inf. Process. Lett. 145: 48-52 (2019)

Conference Papers

1. C. H. Papadimitriou, “Testing Mixed Graphs for Unicursality”, Conference on Algorithms and Complexity, Pittsburgh, 1976 (Abstract in the Proceedings, J.F. Traub (Ed.) and published by Academic Press; see also article 2)

2. C. H. Papadimitriou, “The Complexity of the Local Structure of Certain Convex Polytopes,” Proc. 1976 CISS Conference, Baltimore, 1976.

3. C. H. Papadimitriou, K. Steiglitz,“Some Complexity Results on the Traveling Salesman Problem”, Proc. 1976 STOC (see also Articles 3 and 5).

4. C. H. Papadimitriou, K. Steiglitz, “Traps for Traveling Salesmen”, ORSA-TIMS Meeting, Miami Beach, 1976 (Abstract published in the Proceedings; see also Article 7).

5. C. H. Papadimitriou, “Mixed Graphs, Euler Tours, and Postman Routes,” ORSA-TIMS Meeting, Miami Beach, 1976 (invited paper; Abstract in the Proceedings).

6. C. H. Papadimitriou, P.A. Bernstein, J.B. Rothnie, “Some Computational Problems in Database Concurrency Control”, Proc. Conference on Theor. Comp. Sci., Waterloo, 1976.

7. C. H. Papadimitriou, “The Probabilistic Analysis of Matching Heuristics,” Proc. 15th Allerton Conference, 1977.

8. P.A. Bernstein, C. H. Papadimitriou, J.B. Rothnie “Resolving Certain Concurrent Update Problems without Locking: an Abstract,” Proc. IEEE Workshop on Databases and Operating Systems, Chicago 1977.

9. P.C. Kanellakis, C. H. Papadimitriou, “An Effective Heuristic for the Asymmetric Traveling Salesman Problem,” 1978 ORSA-TIMS Meeting, Los Angeles (abstract was published in the Proceedings; see also Article 19).

10. P.A. Bernstein, N. Goodman, J.B. Rothnie, C. H. Papadimitriou “Analysis of Serializability of SDD-1: A System of Distributed Databases (the Fully Redundant Case),” Proc. 1977 COMSAC, Chicago (see also Article 9).

11. C. H. Papadimitriou, P.C. Kanellakis, “Flowshop Scheduling with Limited Temporary Storage,” Proc. 16th Allerton Conference, 1978 (see also Article 16).

12. C. H. Papadimitriou, M. Yannakakis “The Complexity of Restricted Spanning Tree Problems”, Proc. 1979 ICALP Conference , Springer-Verlag (see also Article 20).

13. M. Yannakakis, C. H. Papadimitriou, H.T. Kung, “Locking Policies: Safety and Freedom from Deadlock,” Proc. 1979 FOCS Conference, Puerto-Rico.

14. C. H. Papadimitriou, “Probabilistic Results for Geometric Optimization,” ORSA-TIMS Meeting, Milwaukee, 1979 (invited paper; abstract in the Proceedings).

15. C. H. Papadimitriou, D.S. Hochbaum, “The $k$-Median Problem: Worst-Case and Probabilistic Results,” Proc. 10th Symposium on Mathematical Programming, Montreal, August 1979 (see also Article 22).

16. H.T. Kung, C. H. Papadimitriou, “An Optimality Theory of Concurrency Control for Databases,” Proc. 1979 SIGMOD Conference, Boston, May 1979 (see also Article 46).

17. R.M. Karp, C. H. Papadimitriou, “On Linear Characterizations of Combinatorial Optimization Problems,” Proc. 1980 FOCS Conference, Syracuse (see also Article 32).

18. M. Yannakakis, C. H. Papadimitriou, “Algebraic Dependencies,” Proc. 1980 FOCS Conference, Syracuse (see also Article 33).

19. W. Lipski, C. H. Papadimitriou, “A Fast Algorithm for Testing for Correctness and Detecting Deadlocks in Locked Transaction Systems,” Proc. 1980 CISS, Princeton (see also Article 23).

20. C. H. Papadimitriou “On the Power of Locking,” Proc. 1981 SIGMOD Conference, Ann Arbor.

21. C. H. Papadimitriou, M. Yannakakis, “Bounds for Planar Independent Sets,” 1981 ORSA-TIMS Meeting, Toronto (invited paper; abstract in the Proceedings).

22. P. Kanellakis, C. H. Papadimitriou, “On the Complexity of Distributed Concurrency Control,” Proc. 1981 FOCS Conference (see also Article 41).

23. C. H. Papadimitriou, M. Yannakakis, “Worst-Case Bounds for Planar Graphs and the Method of Induction on Faces,” Proc. 1981 FOCS Conference (see also Article 42).

24. C. H. Papadimitriou, P.C. Kanellakis, “Concurrency Control Using Multiple Versions,” Proc. 1982 PODS Conference (see also Article 48).

25. N. Megiddo, S. Hakimi, M.R. Garey, D.S. Johnson, C. H. Papadimitriou “The Complexity of Searching a Graph”, Proc. 1981 FOCS Conference (see also Article 49).

26. P.C. Kanellakis, C. H. Papadimitriou, “Is Distributed Locking Harder?” Proc. 1982 PODS Conference (see also Article 39).

27. C. H. Papadimitriou, M. Yannakakis, “The Complexity of Facets (and Some Facets of Complexity),” Proc. 1982 STOC Conference (see also Article 43).

28. C. H. Papadimitriou, M. Sipser, “Communication Complexity,” Proc. 1982 STOC Conference (see also Article 44).

29. C. H. Papadimitriou, “The Complexity of Unique Solutions,” Proc. 1982 FOCS Conference, Chicago (see also Article 50).

30. C. H. Papadimitriou, S. Zachos, “Two Remarks on the Power of Counting,” Proc. 1983 GI Conference, Springer-Verlag, Dortmund.

31. S. Cosmadakis, C. H. Papadimitriou, “Updating Relational Views,” Proc. 1983 PODS Conference, Atlanta (see also Article 51).

32. F. Makedon, C. H. Papadimitriou, I.H. Sudborough, “Topological Bandwidth,” Proc. 1983 CAAP Conference, L'Aquila (see also Article 52).

33. C. H. Papadimitriou, “The Theory of Database Concurrency Control,” Proc. 1983 GI Conference, Springer-Verlag , Dortmund.

34. L. Kirousis, C. H. Papadimitriou, “Pebbling and Searching,” Proceedings of the Conference of Applications of Algebra and Combinatorics in Computer Science, Szeged (see also Article 54).

35. C. H. Papadimitriou, J. Tsitsiklis, “On the Complexity of Designing Distributed Protocols”, Proc. 1983 MELECON Conference, Athens (see also Article 45).

36. C. H. Papadimitriou, “Polytopes and Complexity,” Progress in Combinatorial Optimization , W.R Pulleyblank (Ed.), Academic Press, 1984. (Invited talk at the Silver Jubilee Symposium at Waterloo, 1982).

37. C. H. Papadimitriou, “Games Against Nature,” Proceedings of the 1983 FOCS Conference (see also Article 56).

39. M. Yannakakis, P. Kanellakis, S. Cosmadakis, C. H. Papadimitriou,“Cutting and Partitioning Graphs after a Fixed Pattern,” Proc. 1983 ICALP Conference, Springer Verlag.

40. C. H. Papadimitriou, C. Thanos,“Concurrency Control in Distributed Databases: State of the Art,” Proc. 1983 European Teleinformatics Conference, pp. 369-379.

41. F. Afrati, C. H. Papadimitriou, G. Papageorgiou, “The Complexity of Cubical Graphs,” Proceedings of the 1984 ICALP Conference, Springer Verlag (see also Article 55).

42. C. H. Papadimitriou, J.D. Ullman, “A Time-Communication Tradeoff,”Proceedings of the 1984 FOCS Conference (see also Article 61).

43. C. H. Papadimitriou, M. Yannakakis, “The Complexity of Reliability,” in Proc. 1985 PODS Conference (see also Article 99).

44. T. Hadzilakos, C. H. Papadimitriou, “Algorithmic Aspects of Multiversion Concurrency Control,” Proc. 1985 PODS Conference (see also Article 70).

45. L. Kiroussis, C. H. Papadimitriou, “The Complexity of Recognizing Polyhedral Scenes,” Proc. 1985 FOCS Conference (see also Article 64).

46. C. H. Papadimitriou, D. Wolfe, “The Complexity of Facets Resolved,” Proc. 1985 FOCS Conference (see also Article 75).

47. D.S. Johnson, C. H. Papadimitriou, M. Yannakakis, “How Easy is Local Search?” Proc. 1985 FOCS Conference (see also Article 74).

48. C. H. Papadimitriou, J.N. Tsitsiklis, “On the Stochastic Scheduling of Trees,” Proc. 1985 Allerton Conference (see also Article 67)

49. F. Afrati, C. H. Papadimitriou, G. Papageorgiou, A. Roussou, Y. Sagiv, J.D. Ullman, “On the Convergence of Sideways Information Passing,” Proc. 1985 PODS Conference (see also Article 85).

50. F. Afrati, C. H. Papadimitriou, G. Papageorgiou, “The Synthesis of Communication Protocols,” Proc.1986 PODC Conference (see also Article 78).

51. F. Afrati, C. H. Papadimitriou, “The Parallel Complexity of Simple Logic Programs,” Proc. 1987 PODS Conference (see also Article 87).

52 C. H. Papadimitriou, M. Yannakakis, “Towards an Architecture-Independent Analysis of Parallel Algorithms,” Proc. 1988 STOC (see also Article 90).

53. C. H. Papadimitriou, M. Yannakakis, “Optimization, Approximation, and Complexity Classes” Proc. 1988 STOC (see also Article 89).

54. Ph. Kolaitis, C. H. Papadimitriou, “Why Not Negation by Fixpoint?” Proc. 1988 PODS (see also Article 93).

55. Ph. Kolaitis, C. H. Papadimitriou, “Some Computational Aspects of Circumscription,” Proc. 1988 AAAI Conference (see also Article 94).

56. C. H. Papadimitriou, M. Yannakakis,“Shortest Paths without a Map,'' Proc. of the 1989 ICALP Conference, Springer--Verlag.

57. F. Afrati, C. H. Papadimitriou, G. Papageorgiou, “Scheduling to Minimize Time and Communication”, Proc. 1988 AWOC, Springer--Verlag.

58. C. H. Papadimitriou, M. Sideri, “The Bisection Width of Grid Graphs,'' Proc. 1990 SODA Conference.

59. C. H. Papadimitriou, M. Sideri, “Optimal Majorities in a Network,'' Proc 4th Czechoslovakian Symposium on Combinatorics, Prahastice, 1990.

60. C. H. Papadimitriou, “Inefficient Proofs of Existence and Complexity Classes,'' Proc 4th Czechoslovakian Symposium on Combinatorics, Prahastice, 1990.

61. X. Deng, C. H. Papadimitriou, “Searching an Unknown Graph,” Proc. 1990 FOCS.

62. S. Buss, C. H. Papadimitriou, J. N. Tsitsiklis, “On the Predictability of Coupled Finite Automata: An Allegory on Chaos,” Proc. 1990 FOCS .

63. C. H. Papadimitriou, P. Serafini, M. Yannakakis, “The Communication Capacity of Reserved Lines,'' presented at the 1989 ORSA-TIMS meeting.

64. C. H. Papadimitriou, “On Graph-Theoretic Lemmata and Complexity Classes,'' Proc. 1990 FOCS.

65. C. H. Papadimitriou, M. Sideri, “Optimal Coteries,'' Proc. 1991 PODC .

66. C. H. Papadimitriou, M. Yannakakis, “On the Value of Information in Distributed Decision—Making,'' Proc. 1991 PODC.

67. E. Koutsoupias, C. H. Papadimitriou, M. Sideri, “Optimal bisection of a Polygon,'' Proc. 1990 Computational Geometry Conf.

68. C. H. Papadimitriou, M. Sideri, V. Rangan, “Synthesizing Communication Networks from Trust Specifications,'' Proc. 1991 FST TCS Conference, New Delhi.

69. E. Dahlhaus, D.S. Johnson, C. H. Papadimitriou, P. Seymour, M. Yannakakis,

“The Complexity of Multiway Cuts,” Proc. 1992 STOC, pp. 241--251.

70. C. H. Papadimitriou, M. Yannakakis, “Tie--breaking Semantics and Structural Totality of Logic Programs,” Proc. 1992 PODS.

71. X. Deng, C. H. Papadimitriou, “How to Learn an Unknown Environment,” Proc. 1991 FOCS .

72. C. H. Papadimitriou, “Selecting a Satisfying Truth Assignment,” Proc. 1991 FOCS .

73. X. Deng, C. H. Papadimitriou, “Competitive Distributed Decision-Making,”

Proc. 1992 IFIP Congress, pp. 350--356, Madrid, Spain.

74. A. Sch\” affer, C. H. Papadimitriou, M. Yannakakis “On the Complexity of Local Search,'' Proc. 1990 STOC.

75. C. H. Papadimitriou, M. Sideri, “On Finding Extensions of Default Theories,'' Proc. 1992 ICDT Conference , Berlin, pp. 276--281, Springer-Verlag.

76. C. H. Papadimitriou, M. Yannakakis, “On Limited Nondeterminism and the Complexity of the Vapnic-Chervonenkis Dimension,'' Proc. 1993 Conf. on Structures in Complexity Theory .

77. C. H. Papadimitriou, M. Yannakakis, “Linear Programming without the Matrix,'' Proc. 1993 STOC.

78. D. Kavvadias, C. H. Papadimitriou, M. Sideri, “On Horn Envelopes and Hypergraph Transversals,'' Proc. 1993 ISAAC Conf., pp. 399--405, Springer-Verlag.

79. E. Koutsoupias, C. H. Papadimitriou, “On the $k$-server Conjecture,'' Proc. 1994 STOC.

79. C. H. Papadimitriou, M. Yannakakis, “Complexity as Bounded Rationality,'' Proc. 1994 STOC.

80. G. Gogic, C. H. Papadimitriou, M. Sideri, “Incremental Recompilation of Knowledge,'' Proc. of the 1994 AAAI.

81. E. Koutsoupias, C. H. Papadimitriou,“Beyond Competitive Analysis,'' Proc. 1994 FOCS , pp. 394--400.

82. J. Tsitsiklis, C. H. Papadimitriou, “On the Complexity of Optimal Queuing Network Control,'' Proc. 9th Structure in Complexity Conference, pp. 318-322, 1994.

83. C. H. Papadimitriou, S. Ramanathan, P. V. Rangan, “Information Caching for Delivery of Personalized Video,'' Proc. of International Conference on Multimedia Computing and Systems, pp. 214--223, 1994.

84. C. H. Papadimitriou, P. Raghavan, M. Sudan, H. Tamaki, “Motion Planning on a Graph,'' Proc. 35 FOCS, pp. 511--520, 1994.

85. M. Mihail, C. H. Papadimitriou, “On the Random Walk Method for Protocol Testing,'' Proc. 6th International Conference on Computer-Aided Verification, pp. 132--141, 1994.

86. P. Crescenzi, C. H. Papadimitriou, “Reversible Simulation of Space-Bounded Computations,'' Proc. 4th Italian Conference in Theoretical Com. Sci. , pp. 189--195, 1992.

87. M. Grigni, C. H. Papadimitriou, D. Papadias, “Topological Inference,'' Proc. 1995 IJCAI.

88. G. Gogic, H. Kautz, C. H. Papadimitriou, B. Selman “The Comparative Linguistics of Knowledge Representation,'' Proc. 1995 IJCAI.

89. C. H. Papadimitriou, S. Ramanathan, P. Venkat Rangan, “Optimum Information Delivery,'' Proc. 1995 ISAAC Conference.

90. S. Abiteboul, C. H. Papadimitriou, V. Vianu “The Power of Reflective Relational Machines,'' Proc. 1995 LICS .

91. C. H. Papadimitriou “Database Metatheory: Asking the Big Queries,'' Proc. 1995 PODS (invited talk); also, reprinted in SIGACT NEWS.

92. M. Grigni, E. Koutsoupias, C. H. Papadimitriou “A Polynomial-Time Approximation Scheme for the Planar-Graph TSP,'' Proc. of the 1995 FOCS Conference .

93. C. H. Papadimitriou “NP-Completeness: A Retrospective,'' Proc. of the 1997 ICALP Conference (invited talk).

94. Z. Chen, M. Grigni, C. H. Papadimitriou “Planarity, Revisited,'' Proc. of the 1997 WADS Conference (invited talk).

95. C. H. Papadimitriou, M. Yannakakis “On the Complexity of Database Queries,'' Proc. 1997 PODS.

96. X. Deng, C. H. Papadimitriou, “Decision-Making by Hierarchies of Discordant Agents,'' Proc. 1997 ISAAC Conference.

97. C. H. Papadimitriou, “Computational Approaches to Organization Theory,'' Proc. 1996 ESA (invited talk).

98. J. M. Hellerstein, E. Koutsoupias, C. H. Papadimitriou “On the Analysis of Indexing Schemes,'' Proc. 1997 PODS.

99. C.H. Papadimitriou, “Database Metatheory: Asking the Big Queries,” PODS 1995:1-10

100. E. Koutsoupias, C.H. Papadimitriou, “The 2-Evader Problem,” IPL 57(5): 249-252, 1996.

101. C.H. Papadimitriou, “The Complexity of Knowledge Representation,” Proceedings, Eleventh Annual IEEE Conference on Computational Complexity, pp. 244-248, Philadelphia, Pennsylvania, 24-27, May 1996.

102. C.H. Papadimitriou, D. Suciu, V. Vianu, “Topological Queries in Spatial Databases,” PODS 1996, 81-92.

103. E. Koutsoupias, C.H. Papadimitriou, M. Yannakakis, “Searching a Fixed Graph,” ICALP 1996, 280-289.

104. C.H. Papadimitriou, “Computational Aspects of Organization Theory,” Extended Abstract, ESA 1996, 559-564.

105. M. Grigni, V. Mirelli, C.H. Papadimitriou “On the Difficulty of Designing Good Classifiers,”

COCOON 1996, 273-279.

106. J.M. Hellerstein, E. Koutsoupias, C.H. Papadimitriou “On the Analysis of Indexing Schemes,” PODS 1997, 249-256.

107. C. H. Papadimitriou “Planar Topological Queries,” CDB 1997, Lecture Note in Computer Science, Vol.1191, Springer, 1997: 1-6.

113. C. H. Papadimitriou, “Planar Topological Queries,” CDB 1997, Lecture Notes in Computer Science, Vol.1191, Springer, 1997: 1-6.

108. C.H. Papadimitriou, P. Raghavan, H. Tamaki, S. Vempala “Latent Semantic Indexing: A Probabilistic Analysis,” PODS 1998, 159-168.

109. M. Chen, M. Grigni, C.H. Papadimitriou “Planar Map Graphs,” Proc. 1998 STOC Conference.

110. P. Crescenzi, D. Goldman, C.H. Papadimitriou, A. Piccolboni, M. Yannakakis “On the Complexity of Protein Folding,” Proc. 1998 STOC Conference . One-page abstract appeared in Proc. RECOMB 98 Conference.

P. Crescenzi, X. Deng, C. H. Papadimitriou ``On approximating a scheduling problem'' Proc. APPROX 98 Conference.

121. Christos H. Papadimitriou and Martha Sideri, “Computational Complexity in the Life Sciences,” Proceedings of the 6th International Conference on Artificial Life ({ALIFE}-98), MIT Press, 1998.

111. J. Kleinberg, C.H. Papadimitriou, P. Raghavan “Approximation Algorithms for Segmentation Problems,” Proc. 1998 STOC Conference.

112. D. Goldman, C.H. Papadimitriou, S. Sorin, “Algorithmic Aspects of Protein Structure Similarity,” Proc. 1999 FOCS Conference.

113. D. Goldman, S. Istrail, C.H. Papadimitriou, “Algorithmic Aspects of Protein Structure Similarity,” FOCS 1999: 512-522.

114. G. Gottlob and C.H. Papadimitriou, “On the Complexity of Single-Rule Datalog Queries,” Proceedings of the 6th International Conference of Logic for Programming and Automated Reasoning LPAR-99, Springer.

115. E. Koutsoupias and C. Papadimitriou, “Worst-Case Equilibria,” Proc. 1999 STACS Conference, Springer, 1999.

116. G. Cheung, S. McCanne, C.H. Papadimitriou, “Software Synthesis of Variable-length Code Decoder Using a Mixture of Programmed Logic and Table Lookups,” Data Compression Conference 1999, 121-130.

117. C. H. Papadimitriou and M. Yannakakis “On the Approximability of Trade-Offs and Optimal Access of Web Sources,” Proc. 2000 FOCS Conference.

118. R.M. Karp, E. Koutsoupias and C.H. Papadimitriou and S. Shenker, “Optimization Problems in Congestion Control,” Proc. 2000 FOCS Conference.

119. J. Feigenbaum and C.H. Papadimitriou and S. Shenker, “Sharing the Cost of muliticast transmissions,” Proc. 2000 STOC Conference.

120. C.H. Papadimitriou and S. Vempala, “On the Approximability of the Traveling Salesman Problem,” Proc. 2000 STOC Conference.

121. J.M. Kleinberg, C.H. Papadimitriou and P. Raghavan, “Auditing Boolean Attributes,” Proc. 2000 PODS Conference (best paper award).

122. C.H. Papadimitriou, “On Certain Rigorous Approaches to Data Mining,” Proceedings of the 6th SIGKDD International Conference on Knowledge Discovery and Data Mining KDD-00, 2000 (invited, abstract only).

123 C.H. Papadimitriou, “Topological Queries”, pp. 3-4, Proc. 6th Int. Symp. Advances in Spatial Databases, SSD, Springer, 1999.

124. C.H. Papadimitriou, “Theoretical Problems Related to the Internet,” COCOON 2000, 1-2 (invited talk, abstract only).

125. C.H. Papadimitriou, “Algorithms, Games, and the Internet.” Proc. STOC 2001 749-753; also, summary in Proc. ICALP 2001: 1-3.

126. C.H. Papadimitriou, M. Yannakakis, “Multiobjective Query Optimization,” Proc. PODS 2001.

127. C.H. Papadimitriou, “Game Theory and Mathematical Economics: A Theoretical Computer Scientist's Introduction,” FOCS 2001, 4-8 (invited tutorial).

128. C.H. Papadimitriou, “Game Theory, Algorithms, and the Internet,” Proc. SODA 2001, 391 (invited talk, abstract only).

129. C.H. Papadimitriou “The Internet, the Web, and Algorithms,” LATIN 2002: 2 (invited talk, abstract only).

130. C.H. Papadimitriou: “Understanding the Internet,” SETN 2002: 1-2 (invited talk, abstract only).

131. J. Feigenbaum, C.H. Papadimitriou, R. Sami, S. Shenker, “A BGP-Based Mechanism for Lowest-Cost Routing,” Proc. 2002 PODC.

132. J. Kleinberg, C. H. Papadimitriou, P. Raghavan, “On the Value of Private Information,” TARK 2001.

133. A. Fabrikant, E. Koutsoupias, C. H.Papadimitriou, “Heuristically Optimized Trade-offs,” Proc. 2002 ICALP.

134. D. Xiaotie, C. H. Papadimitriou, M. Safra, “On the Complexity of Equilibria,” STOC 02.

135. C.H. Papadimitriou, “The Joy of Theory,” Proc. 2002 STOC (Knuth Prize lecture, one-page abstract).

136. A. Akella, S. Seshan, R.M. Karp, S. Shenker, C.H. Papadimitriou, “Selfish Behavior and Stability of the Internet: A Game-Theoretic Analysis of TCP,” SIGCOMM 2002, 117-

137. M. Mihail, C.H. Papadimitriou, “On the Eigenvalue Power Law,” RANDOM 2002, 254-262

138 J. Feigenbaum, C.H. Papadimitriou, R. Sami, S. Shenker, “A BGP-Based Mechanism for Lowest-Cost Routing,” PODC 2002, 173-182

139 A. Fabrikant, E. Koutsoupias, C.H. Papadimitriou, “Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet,” ICALP 2002, 110-122, 237.

140 A. Akella, S. Seshan, R.M. Karp, S. Shenker, C.H. Papadimitriou, “Selfish Behavior and Stability of the Internet: a Game-Theoretic Analysis of TCP,” SIGCOMM 2002: 117-130.

141 N.R. Devanur, C. H. Papadimitriou, A. Saberi, V.V. Vazirani, “Market Equilibrium via a Primal-Dual-Type Algorithm,” FOCS 2002, 389-395

142 A. Archer, C.H. Papadimitriou, K. Talwar, É. Tardos, “An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents,” SODA 2003, 205-214, 245.

143 A. Fabrikant, A. Luthra, E. Maneva, C.H. Papadimitriou, S. Shenker, “On a Network Creation Game,” PODC 2003, 347-351.

144 C. H. Papadimitriou, “The New Problems,” PCK50, 2003, 10, 247.

145 A. Rao, C.H. Papadimitriou, S. Shenker, I. Stoica, “Geographic Routing Without Location Information,” MOBICOM 2003, 96-108.

146 M. Mihail, C.H. Papadimitriou, A. Saberi, “On Certain Connectivity Properties of the Internet Topology. FOCS 2003, 28-35, 249.

147 A. Fabrikant, C.H. Papadimitriou, K. Talwar, “The Complexity of Pure Nash Equilibria,” STOC 2004, 604-612, 252.

148 B.-G. Chun, K. Chaudhuri, H. Wee, M. Barreno, C.H. Papadimitriou, J. Kubiatowicz, “Selfish Caching in Distributed Systems: A Game-Theoretic Analysis,” PODC 2004, 21-30, 253.

149 J. Elson, R.M. Karp, C.H. Papadimitriou, S. Shenker, “Global Synchronization in Sensornets,” LATIN 2004, 609-624.

150 C.H. Papadimitriou, D. Ratajczak, “On a Conjecture Related to Geometric Routing,” ALGOSENSORS 2004, 9-17, 255.

151 M. Feldman, C.H. Papadimitriou, J. Chuang, and I. Stoica, “Free-Riding and Whitewashing in Peer-to-Peer Systems,” ACM SIGCOMM'04 Workshop on Practice and Theory of Incentives in Networked Systems (PINS), pp. 228 – 236, 2004.

152 G. Kouroupas, E. Koutsoupias, C.H. Papadimitriou, M. Sideri, “An Economic Model of the Worldwide Web,” WWW (Special interest tracks and posters) 2005, 934-935.

153 G. Kouroupas, E. Koutsoupias, Christos H. Papadimitriou, M. Sideri, “Experiments with an Economic Model of the Worldwide Web,” WINE 2005, 46-54.

154 C.H. Papadimitriou, “Recent Developments in Equilibria Algorithms,” WINE 2005: 1-2.

155 C. H. Papadimitriou, “Computing Correlated Equilibria in Multi-Player Games,” STOC 2005, 49-56.

156 C.H. Papadimitriou, T. Roughgarden, “Computing Equilibria in Multi-Player Games” SODA 2005: 82-91.

157 C.H. Papadimitriou, S. Safra, “The Complexity of Low-Distortion Embeddings Between Point Sets,” SODA 2005, 112-118.

158 C. Daskalakis, C.H. Papadimitriou, “The Complexity of Games on Highly Regular Graphs,” ESA 2005, 71-82.

159 V. Koltun, C.H. Papadimitriou, “Approximately Dominating Representatives,” ICDT 2005, 204-214.

160 C.H. Papadimitriou, “Algorithmic Problems in Ad Hoc Networks,” DCOSS 2005, 1.

161 C. H. Papadimitriou, “Games Other People Play,” CONCUR 2005, 5.

162 P.W. Goldberg, C.H. Papadimitriou, “Reducibility Among Equilibrium Problems,” STOC 2006.

163 C. Daskalakis, P.W. Goldberg, C.H. Papadimitriou, “The Complexity of Computing a Nash Equilibrium,” STOC 2006.

164 A. Hall, C.H. Papadimitriou, “Approximating the Distortion,” APPROX-RANDOM 2005, 111-122.

165 P. Gopalan, P.G. Kolaitis, E.N. Maneva, C.H. Papadimitriou, “The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies,” ICALP 2006, 346-357.

166 C. Daskalakis, C.H. Papadimitriou, “Computing pure Nash Equilibria in Graphical Games via Markov Random Fields,” ACM Conference on Electronic Commerce 2006, 91-99, 2006.

167 Constantinos Daskalakis, Alex Fabrikant, Christos H. Papadimitriou, “The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games,” ICALP 2006, 513-524.

168. M. Babaioff, R. Kleinberg, C. H. Papadimitriou, “Congestion Games with Malicious Players,” ACM Conference on Electronic Commerce 2007, 103-112.

169. C. Daskalakis, A. Mehta, C. H. Papadimitriou, “Progress in Approximate Nash Equilibria,” ACM Conference on Electronic Commerce 2007, 355-358.

170. C. Daskalakis, C. H. Papadimitriou, “Computing Nash Equilibria in Anonymous Games,”2007 FOCS.

171. A. Hall, E. Nikolova, C.H. Papadimitriou, “Incentive-Compatible Interdomain Routing with Linear Utilities,” 2007 WINE.

172. H. Lin, C. Amanatidis, M. Sideri, R.M. Karp, C.H. Papadimitriou, “Linked Decompositions of Networks and Polya Urns with Choice,” 2008 SODA.

173. A. Fabrikant, C.H. Papadimitriou, “The Complexity of Game Dynamics,” 2008 SODA.

174. C. Borgs, Jennifer T. Chayes, N. Immorlica, A. T. Kalai, Vahab S. Mirrokni, C. H. Papadimitriou “The Myth of the Folk Theorem,” STOC 2008, pp. 365-372.

175. C. H. Papadimitriou “The Search for Equilibrium Concepts.” SAGT 2008.

176. C. Daskalakis, C.H. Papadimitriou “Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games,” FOCS 2008.

177. Christos H. Papadimitriou, Gregory Valiant: A New Look at Selfish Routing. ICS 2010: 178-187

178. Constantinos Daskalakis, Rafael Frongillo, Christos H. Papadimitriou, George Pierrakos, Gregory Valiant: On Learning Algorithms for Nash Equilibria. SAGT 2010: 114-125

179. Constantinos Daskalakis, Christos H. Papadimitriou: On oblivious PTAS's for nash equilibrium. STOC 2009: 75-84

180. Ilan Adler, Constantinos Daskalakis, Christos H. Papadimitriou: A Note on Strictly Competitive Games. WINE 2009: 471-474

181. Constantinos Daskalakis, Christos H. Papadimitriou: On a Network Generalization of the Minmax Theorem. ICALP (2) 2009: 423-434

182. Christos H. Papadimitriou, Christopher A. Wilkens “Economies with non-convex production and complexity equilibria,”ACM Conference on Electronic Commerce 2011: 137-146.

183. Amos Fiat, Christos H. Papadimitriou: When the Players Are Not Expectation Maximizers. SAGT 2010: 1-14

184. Constantinos Daskalakis, Christos H. Papadimitriou: Continuous Local Search. SODA 2011: 790-804

185. Christos H. Papadimitriou, George Pierrakos: On optimal single-item auctions. STOC 2011: 119-128

186. Ilias Foudalis, Kamal Jain, Christos H. Papadimitriou, Martha Sideri: Modeling Social Networks through User Background and Behavior. WAW 2011: 85-102

187. David Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer, Christopher Umans: Inapproximability for VCG-Based Combinatorial Auctions. SODA 2010: 518-536.

188. Christos H. Papadimitriou, Gregory Valiant: A New Look at Selfish Routing. ICS 2010: 178-187.

189. Amos Fiat, Christos H. Papadimitriou: When the Players Are Not Expectation Maximizers. SAGT 2010: 1-10

190. Constantinos Daskalakis, Rafael M. Frongillo, Christos H. Papadimitriou, George Pierrakos, Gregory Valiant: On Learning Algorithms for Nash Equilibria. SAGT 2010: 114-125

191. David Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer, Christopher Umans: Inapproximability for VCG-Based Combinatorial Auctions. SODA 2010: 518-536

192. Constantinos Daskalakis, Christos H. Papadimitriou: Continuous Local Search. SODA 2011: 790-804.

193. Christos H. Papadimitriou, George Pierrakos: On optimal single-item auctions. STOC 2011: 119-128.

194. Ilias Foudalis, Kamal Jain, Christos H. Papadimitriou, Martha Sideri: Modeling Social Networks through User Background and Behavior. WAW 2011: 85-102.

195. Christos H. Papadimitriou: Games, algorithms, and the Internet. WWW 2011: 5-6.

196. Shahar Dobzinski, Christos H. Papadimitriou, Yaron Singer: Mechanisms for complement-free procurement. EC 2011: 273-282.

197. Christos H. Papadimitriou, Christopher A. Wilkens: Economies with non-convex production and complexity equilibria. EC 2011: 137-146

198. Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani: The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. FOCS 2011: 67-76

199. Ilias Diakonikolas, Christos H. Papadimitriou, George Pierrakos, Yaron Singer: Efficiency-Revenue Trade-Offs in Auctions. ICALP (2) 2012: 488-499.

200. Christos H. Papadimitriou: The New Faces of Combinatorial Optimization. ISCO 2012: 19-23

201. Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani: Multiplicative updates in coordination games and the theory of evolution. ITCS 2013: 57-58

202. Azza Abouzied, Dana Angluin, Christos H. Papadimitriou, Joseph M. Hellerstein, Avi Silberschatz: Learning and verifying quantified boolean queries by example. PODS 2013: 49-60

203. Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Gregory Valiant, Andrew Wan:

Satisfiability and Evolution. FOCS 2014: 524-530

204. Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani:

Algorithms, Games, and Evolution (Invited Talk). FSTTCS 2014: 45-46

205. Ilan Adler, Christos H. Papadimitriou, Aviad Rubinstein:

On Simplex Pivoting Rules and Complexity Theory. IPCO 2014: 13-24

206. Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein:

The complexity of fairness through equilibrium. EC 2014: 209-226

207. Yang Cai, Christos H. Papadimitriou: “Simultaneous bayesian auctions and computational complexity,”. EC 2014: 895-910.

208. Yang Cai, Constantinos Daskalakis, Christos H. Papadimitriou

“Optimum Statistical Estimation with Strategic Data Sources,” COLT 2015: 280-296 (2015)

209. Christos H. Papadimitriou, Santosh Vempala: “Cortical Learning via Prediction,” COLT 2015: 1402-1422 (2015)

210. Christos H. Papadimitriou, Santosh S. Vempala: Cortical Computation. PODC 2015: 1-2 (2015)

211. Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Gregory Valiant, Andrew Wan:

Satisfiability and Evolution. FOCS 2014: 524-530 (2014)

212. Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani:

Algorithms, Games, and Evolution FSTTCS 2014: 45-46 (2014).

213. Ilan Adler, Christos H. Papadimitriou, Aviad Rubinstein:

On Simplex Pivoting Rules and Complexity Theory. IPCO 2014: 13-24 (2014)

214. Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein:

The complexity of fairness through equilibrium. EC 2014: 209-226 (2014)

215. Yakov Babichenko, Christos H. Papadimitriou, Aviad Rubinstein “Can Almost Everybody be Almost Happy?” ITCS 2016: 1-9 (2016)

216 . Moritz Hardt, Nimrod Megiddo, Christos H. Papadimitriou, Mary Wootters “Strategic Classification,” ITCS 2016: 111-122 (2016)

217. Christos H. Papadimitriou, Georgios Piliouras “From Nash Equilibria to Chain Recurrent Sets: Solution Concepts and Topology,” ITCS 2016: 227-235 (2016)

218. Christos H. Papadimitriou, Nisheeth K. Vishnoi “On the Computational Complexity of Limit Cycles in Dynamical Systems,” ITCS 2016: 403-412 (2016).

219. Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer “Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions.” SODA 2016: 414-429 (2016)

220. Christos H. Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein

“On the Complexity of Dynamic Mechanism Design,” SODA 2016: 1458-1475 (2016)

221. C. Daskalakis, C. Papadimitriou, C. Tzamos “Does Information Revelation Improve Revenue?,”Proceedings of the 2016 ACM Conference on Economics and Computation, pp. 233-250, 2016.

222. G. Kouroupas, E. Markakis, C. Papadimitriou, V. Rigas, M. Sideri “The Web Graph as an Equilibrium,” International Symposium on Algorithmic Game Theory, p. 203-215, 2015.

| | | |

|223. X. Deng, .Z Feng, C. Papadimitriou Power-Law Distributions in a Two-sided Market and Net Neutrality, International Conference on Web | | |

|and Internet Economics, 59-72, 2016. | | |

| | | |

|224. A Livnat, C Papadimitriou, “Evolution and learning: used together, fused together. A response to Watson and Szathmáry,” Trends in | | |

|Ecology & Evolution 31 (12), 894-896, 2016 | | |

| | | |

225. R Legenstein, CH Papadimitriou, S Vempala, W Maass, “Assembly pointers for variable binding in networks of spiking neurons,” CoCo at NIPS, 2016.

|226. C Wu, K Shankari, E Kamar, R Katz, D Culler, C Papadimitriou, E Horvitz, | | |

|Optimizing the diamond lane: A more tractable carpool problem and algorithms, IEEE Intelligent Transportation Systems (ITSC), 2016. | | |

| | | |

| | | |

227. S. Gaspers, C. Papadimitriou, S. H. Sæther, J. A. Telle “MACROBUTTON HTMLDirect [pic]On satisfiability problems with linear structure,” 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016.

228. Panayotis Mertikopoulos, Christos H. Papadimitriou, Georgios Piliouras:

Cycles in Adversarial Regularized Learning. SODA 2018: 2703-2717.

229. Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Mohammad Mahdian, Christos H. Papadimitriou, Ronald L. Rivest, Saeed Seddighin, Philip B. Stark, From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games. SODA 2018: 2291-2310.

230. Maximilian Haas-Heger, Christos H. Papadimitriou, Mihalis Yannakakis, Garud Iyengar, Matei T. Ciocarlie: Passive Static Equilibrium with Frictional Contacts and Application to Grasp Stability Analysis. Robotics: Science and Systems (2018).

231. Robert A. Legenstein, Wolfgang Maass, Christos H. Papadimitriou, Santosh Srinivas Vempala: Long Term Memory and the Densest K-Subgraph Problem. ITCS 2018: 57:1-57:15

232. Paul W. Goldberg, Christos H. Papadimitriou: Towards a Unified Complexity Theory of Total Functions. ITCS 2018: 37:1-37:20

233. Christos Papadimitriou and Santosh Vempala, Random projection in the brain and computation by assemblies of neurons, ITCS 2019.

234. Kurtulus Gemici, Elias Koutsoupias, Barnabé Monnot, Christos H. Papadimitriou, Georgios Piliouras: Wealth Inequality and the Price of Anarchy. STACS 2019: 31:1-31:16

Patent

(With Venkat Rangan and Srinivas Ramanathan) “System for multimedia information delivery,'' 1022.004CIP.

Invited Talks

1976: M.I.T., Columbia, Harvard, Purdue, Bell Laboratories, Carnegie-Mellon, Univ. of Illinois at Urbana-Champaign, I.B.M. Yorktown Heights, Univ. of Rochester.

1977: Univ. of Toronto, M.I.T. (twice), Brown Univ., SUNY at Albany.

1978: M.I.T., UC Berkeley, Carnegie-Mellon.

1979: Univ. of California Santa Barbara, Univ. of Texas Austin, Pennsylvania State Univ., Universite Catholique de Louvain, Univ. of Bonn, Univ. of Frankfurt, Univ. of Wroclaw Poland, Polish Academy of Sciences, Czechoslovakian Academy of Sciences, Univ. of Pisa.

1980: Berkeley, I.B.M. San Jose, Xerox PARC, Stanford Univ., Erasmus Univ. Rotterdam, Yale Univ. (twice), Boston Univ.

1981: Oberwolfach Seminar on Efficient Algorithms, INRIA France, Harvard Univ., National Technical Univ. of Athens, Univ. of Turku Finland, Univ. of Toronto, Univ. of Pisa, Univ. of California San Diego, Irvine, Univ. of Maryland, Seminar of Theoretical Issues in Databases Cetraro Italy, Brown Univ. (Distinguished Lecturer Series).

1982: Univ. of Rome, Politecnico di Milano, Univ. of California Santa Barbara, Stanford, M.I.T.

1983: Hungarian Academy of Sciences, Bell Laboratories, School in Combinatorial Optimization (NIHE, Ireland), School in Computer Systems Theory (Udine, Italy).

1984: San Jose State Univ., Universitat Bonn, Democritos Univ. of Thrace, Greece, Univ. of Paderborn, F.R. Germany.

1985: Univ. California, Santa Barbara, M.I.T., Georgia Institute of Technology (centennial speaker), University of Texas at Austin.

1986: Institute of Software Academia Sinica, Univ. of Patras, Workshop on Game Theory (Northwestern), AT\&T Bell Laboratories, Yale University, UCLA, Rice University, IIT Delhi, Conference on Foundations of Software Theory and Theoretical Computer Science.

1987: Univ. of California at Santa Barbara, Rutgers University, Cornell University, Univ. of California at San Diego, Rice University, Princeton University.

1988: Princeton University, Columbia University, Univ. of Illinois at Urbana--Champaign, Univ. of Bonn.

1989: M.I.T. (three colloquia), Counting and Coding II (Paris, France).

1990: International Congress on Information Theory, Princeton, Georgia Institute of Technology, University of Toronto.

1991: Purdue University, University of Maryland, Columbia University, Harvard, M.I.T., Boston University, BellCore, IBM Yorktown, ATT Bell Labs, IIT Delhi, 20th Anniversary Symposium (Erice Italy), Math. Programming Symposium (Amsterdam), York Univ., Univ. of Bonn.

1992: World Congress of Economics, Moscow, MIT, Univ. of Rome.

1993: USC (Distinguished Lecture Series), Caltech, UCSD Dept. of Economics, Univ. of Rome, IBM Japan, ISAAC (Hong Kong).

1994: University of California Berkeley, Stanford CS, Stanford OR, University of California Santa Barbara (Distinguished Lecture Series), Princeton University, Cornell University.

1995: PODS 95.

1996: ESA 96, TARK 96, Hong Kong Univ. of Science and Technology, Stanford Univ.

1997: Delphi Workshop on Constraints, CIAC 97, WADS 97, ICALP 97, Univ. of Rome, Univ. of Venice, Northwestern Univ., M. I. T., Brown (Distinguished Lecture Series), Univ. of Washington (Distinguished Lecture Series),City U. of Hong Kong, Hong Kong Univ. of Science and Technology, ETH Zurich, Univ. of Patras.

1998: University of Kentucky, Univ. of Central Florida. (Distinguished Lecture Series), Univ. of Massachusetts, Amherst (Distinguished Lecture Series), Stanford Univ., COCOON 98 (Taipei).

1999: ICDT 1999 (Jerusalem), AT&T Labs (Distinguished Lecture Series).

2000: ISAAC 2000 (Sydney), Univ. of Central Florida, MIT (Distinguished Lecture Series), MIT OR Center, KDD-2000, Univ. of North Carolina (Distinguished Lecture Series), UCSC (Distinguished Lecture Series).

2001: Univ. of Florida (Distinguished Lecture Series), UCLA (Marshak Lecture), Georgia Tech. (Distinguished Lecture Series), Santa Clara Univ. (Distinguished Lecture Series), Univ. of Washington, Microsoft Research, University of Pittsburgh (Distinguished Lecture Series)

2002: Harvard, MIT, University of Toronto (Distinguished Lecture Series), University of Illinois at Chicago (Distinguished Lecture series), LATIN (Cancun), European Symp. on Algorithms (Rome), Athens Institute of Technology inauguration (keynote speaker), Brown University (Kanellakis Lecture), Harvard DEAS.

2003: Univ. of Maryland (Distinguished Lecture Series), MIT Mathematics, Sonoma State Univ., Carnegie-Mellon Univ. (Distinguished Lecture Series), Univ. of San Francisco.

2004: Institute for Advanced Studies (Princeton), Univ. of Utrecht, Ecole Nationale Supérieure (Paris, series of 4 lectures), Microsoft Research, Harvard University.

2005: Institute for Advanced Studies (Princeton), UT Dallas (Distinguished Lecture Series), Ecole Normale Supérieure (Paris, series of 3 lectures), WINE (Hong Kong), Stanford, CONCUR, Univ. of Athens.

2006: Yahoo (Distinguished Lecture Series), Princeton, Rutgers (Distinguished Lecture Series), Google-New York, Stanford (Business School Economics Seminar), Microsoft Research.

2007: UPC (Barcelona), Yahoo Research – Barcelona, Ecole Normale Superieure (Paris), NYU (Business School), IAS, MIT, MIT OR Center, Microsoft Research, ALGO conference, WINE conference, San Diego, Stanford University, UCSD (Distinguished Lecturer).

2008: MIT (Derrouzos Lecture), Microsoft New England, Tsinghua University, ETH (Hurwitz Lectures), CMU (Katayanagi Lecture), Princeton University, Tokyo Technological University.

2009: Columbia University, Stanford University, Microsoft Research, WADS conference (Banff, Canada), Tsinghua University (China 2020 Vision Distinguished Speaker), EPFL Lausanne, US Naval Academy (Michelson Memorial Lecture).

2010: University of Liverpool, Microsoft Research (Seattle and Cambridge), Max Planck Institute (Saarbrucken), City University of Hong Kong, SUNY Stony Brook (Distinguished Lecture Series), University of Athens, Athens Polytechnic, Univesity of Cyprus.

2011: Polytechnic University of Catalonia, Hebrew University, Tsinghua University, WWW Conference (Hyderabad, India), Hebrew University, MIT, University of Toronto (Distinguished Lecture), ETH (Distinguished Lecturer).

2012: Tsinghua University, Beijing (Distinguished Lecturer), Stanford (Distinguished Lecturer), Princeton, MIT, UCF, Univ. of Bergen, Norway, Univ. of Aarhus, Denmark.

2013: Peking University, EPFL (Lausanne), Microsoft Research New England, Harvard, UCSD, NYC Econ Day, UCSF.

2014: Univ. de Paris Dauphine (distinguished lecture), Renaissance Research (distinguished lecture), UCSC (distinguished lecture), Columbia, Vienna Summer in Logic, UC Santa Barbara (distinguished lecture), Microsoft Research Asia (Beijing).

2015: Univ. of Southampton, Univ. Autonoma de Catalunya (Spain), Univ. of Bergen (Norway), EPFL (Lausanne, Switzerland), Univ. de Grenoble (France), PODC (San Sebastian), USC, TU Graz (Austria), EECS Colloquium (Berkeley).

2016. SWAT Symposium (Reykjavik), Games 2016 (Maastricht), ETH (Zurich).

2017. University of British Columbia (distinguished lecture), Duke (distinguished lecture), Kailath Colloquium (Stanford), CIAC (Athens), Columbia, Rutgers (distinguished lecture), Santa Fe Institute, TU Graz, ICTS (India, 10th anniversary speaker), IISc India, NCBS (India).

2018. MIT (distinguished lecture), Tel Aviv University (PCP Fest), IRIF Paris, ECCO symposium, Freiburg, Rutgers University (Distinguished Lecture), Theory Day NYC, Princeton Theory Seminar, Google NY seminar, IISc Bangalore (series of three lectures)

2019. Princeton Univ (OR department distinguished lecture), Microsoft India, TTIC (Distinguished lecture), Purdue (50th anniversary speaker).

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download