Dimitris Paparas

My name is Dimitris Paparas (Greek: Δημήτρης Παπάρας) and I am a theory PhD student at the Computer Science department of Columbia University. My advisor is Prof. Mihalis Yannakakis. Prior to that, I received a BSc in Computer Science and Telecommunications and a MSc in Theoretical Computer Science, both from the Department of Informatics and Telecommunications of the University of Athens, Greece. My supervisor was Prof. Elias Koutsoupias.

Research Interests

My research lies in the area of Theoretical Computer Science. In particular, I am interested in the following topics: My PhD focuses on Computational Economics with an emphasis on Equilibrium Computation. In particular, I am interested in algorithmic and complexity results regarding the computation of Arrow-Debreu and Fisher equilibrium in various settings. My goal is to understand whether there is a basic property that utility functions must have to allow polynomial time algorithms for finding an (approximate) equilibrium and whether finding an equilibrium is hard for utilities lacking this property. A closely related question is whether there exists a necessary and sufficient condition for utility functions to satisfy in order for the equilibrium to be expressed as a Convex Program, yielding polynomial time (approximation) algorithms. If you find these questions interesting, here is a related paper.

Finally, I am also interested in the related area of Algorithmic Mechanism Design. Specifically, I enjoy working on the problem of revenue maximization in various auction settings. Here is a related paper.


  1. On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms, Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis, FOCS 2015 [conference version]
  2. On-Line Profit-Maximization Algorithms for Managing Sponsored Content in Cellular Networks, Matthew Andrews, Yigal Bejerano, Dimitris Paparas, Evangelia Skiani, 4th Smart Data Pricing (SDP) Workshop, 2015 [conference version]
  3. The Complexity of Optimal Multidimensional Pricing, Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis, SODA 2014 [arxiv, conference version]
  4. The Complexity of Non-Monotone Markets, Xi Chen, Dimitris Paparas, Mihalis Yannakakis, STOC 2013 [arxiv, conference version]
  5. Clustering on k-Edge-Colored Graphs, Eric Angel, Evripidis Bampis, Alexander Kononov, Dimitris Paparas, Emmanouil Pountourakis, Vassilis Zissimopoulos , MFCS 2013 [conference version]
  6. Flexible Use of Cloud Resources through Profit Maximization and Price Discrimination, Konstantinos Tsakalozos, Herald Kllapi, Evangelia Sitaridi, Mema Roussopoulos, Dimitris Paparas, Alex Delis, ICDE 2011 [conference version]


The best way to reach me is via e-mail at my_last_name@cs.columbia.edu