I am on the job market. After defending my thesis this coming August, I will join UW Madison for a two years Postdoc with Shuchi Chawla.
My name is Dimitris Paparas (Greek: Δημήτρης Παπάρας) and I am a final year 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 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.
- Complexity Theory
- Computational Economics / Algorithmic Game Theory
I am also interested in the related area of Algorithmic Mechanism Design. In more details, my work aims to understand whether it is possible to generalize the work of Myerson
to multi-dimensional settings where there is one seller, one buyer, and n items. A nice property of Myerson’s result is that it provides a closed-form characterization
(and thus an efficient algorithm) for the optimal auction when selling one product to many buyers. Is there a closed form characterization for the multi-dimensional setting too?
Relaxing the requirement for a closed form characterization, is there an efficient
algorithm that implements the optimal auction for the multi-dimensional setting? If you find these questions interesting, this and this are two related papers.
- 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]
- 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]
- The Complexity of Optimal Multidimensional Pricing, Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis, SODA 2014 [arxiv, conference version]
- The Complexity of Non-Monotone Markets, Xi Chen, Dimitris Paparas, Mihalis Yannakakis, STOC 2013 [arxiv, conference version]
- Clustering on k-Edge-Colored Graphs, Eric Angel, Evripidis Bampis, Alexander Kononov, Dimitris Paparas, Emmanouil Pountourakis, Vassilis Zissimopoulos , MFCS 2013 [conference version]
- 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 Complexity of Non-Monotone Markets, Xi Chen, Dimitris Paparas, Mihalis Yannakakis, Journal of ACM (Accepted and currently under revision)
- The Complexity of Optimal Multidimensional Pricing, Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis, Games and Economic Behavior (Accepted and currently under revision)
Manuscripts in Preparation
- Rank 2 Bimatrix Games are PPAD-hard, Xi Chen, Anthi Orfanou, Dimitris Paparas, Mihalis Yannakakis
- Approximating the actual Equilibrium in Markets with GS utilities, Dimitris Paparas, Mihalis Yannakakis
The best way to reach me is via e-mail at email@example.com