Dimitris Paparas

My name is Dimitris Paparas (Greek: Δημήτρης Παπάρας). I am a Software Engineer at Google Research where I am a member of the Dataset Search team. Our goal is to enable users find datasets stored across the Web through a simple keyword search. Prior to that, I was with Google Cloud where I designed and implemented algorithms that manage the deployment, upgrade, and decommission of machines in Google's data centers. Before joining Google, I was a Postdoctoral Research Scientist at the University of Wisconsin-Madison working with Shuchi Chawla. I obtained a PhD in Theoretical Computer Science from the Computer Science department of Columbia University, where I was extremely lucky to collaborate with Mihalis Yannakakis, who was also my advisor, and Xi Chen. In the distant past, I also 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.

Research Interests

My research lies in the area of Theoretical Computer Science. In particular, I am interested in the following topics:

Conference Papers

  1. Dataset or Not? A study on the veracity of semantic markup for dataset pages, Tarfah Alrashed, Dimitris Paparas, Omar Benjelloun, Ying Sheng, Natasha Noy, ISWC 2021 [conference version][Best Student Paper Award]
  2. On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer, Xi Chen, George Matikas, Dimitris Paparas, Mihalis Yannakakis, SODA 2018 [arxiv]
  3. 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]
  4. 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]
  5. The Complexity of Optimal Multidimensional Pricing, Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis, SODA 2014 [arxiv, conference version]
  6. The Complexity of Non-Monotone Markets, Xi Chen, Dimitris Paparas, Mihalis Yannakakis, STOC 2013 [arxiv, conference version]
  7. Clustering on k-Edge-Colored Graphs, Eric Angel, Evripidis Bampis, Alexander Kononov, Dimitris Paparas, Emmanouil Pountourakis, Vassilis Zissimopoulos, MFCS 2013 [conference version]
  8. 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]

Journal Articles

  1. On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer, Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis, SIAM J. Comput. 51(3): 492-548 (2022)
  2. The Complexity of Optimal Multidimensional Pricing for a unit-demand buyer, Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis, Games and Economic Behavior 110: 139-164 (2018) [pdf]
  3. The Complexity of Non-Monotone Markets, Xi Chen, Dimitris Paparas, Mihalis Yannakakis, J. ACM 64(3): 20:1-20:56 (2017) [pdf]
  4. Clustering on k-Edge-Colored Graphs, Eric Angel, Evripidis Bampis, Alexander Kononov, Dimitris Paparas, Emmanouil Pountourakis, Vassilis Zissimopoulos, Discrete Applied Mathematics 211: 15-22 (2016) [pdf]

Manuscripts

  1. Searching, Sorting, and Cake Cutting in Rounds, Simina Brânzei, Dimitris Paparas, Nicholas Recker
  2. Pricing for Online Resource Allocation: Beyond Subadditive Values, Shuchi Chawla, Benjamin Miller, Dimitris Paparas, Yifeng Teng [arxiv]
  3. Rank 2 Bimatrix Games are PPAD-hard, Xi Chen, Anthi Orfanou, Dimitris Paparas, Mihalis Yannakakis
  4. Approximating the actual Equilibrium in Markets with GS utilities, Dimitris Paparas, Mihalis Yannakakis

PhD Thesis

Contact

The best way to reach me is via e-mail at X@gmail.com where X is the only word generated by the context free grammar {X -> YZ, Y -> ek, Z -> dimpap}. You can also reach me at my work email at first_letter_of_first_name_followed_by_last_name@google.com