Research

I graduated recently from Georgia Tech with a PhD in the ACO program and my advisor was Richard Lipton. I am now doing a postdoc at the University of Toronto. My research interests lie in the areas of Analysis of Algorithms, Approximation Algorithms, Game Theory, Auction Design and Machine Learning. Most of my work in the last few years has focused on algorithmic questions that arise in the context of Game Theory and Economics such as computation of equilibria or allocations of indivisible goods.

My resume

Publications:

  • H. Hatami, A. Magen, E. Markakis. Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics. Manuscript.
  • R. Lipton, E. Markakis, A. van den Essen. Some Remarks on the Jacobian Conjecture and Connections with Hilbert's Irreducibility Theorem. Manuscript.
  • S. Khot, R. Lipton, E. Markakis, A. Mehta. Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions. Workshop on Internet and Network Economics (WINE), pp. 92-101, 2005, invited for submission to Algorithmica.
  • M. Kolountzakis, E. Markakis, A. Mehta. Learning Symmetric Juntas in time n^{o(k)}. In the proceedings of "Interface between Harmonic Analysis and Number Theory", 2005.
  • E. Markakis. Computational Aspects of Game Theory and Microeconomics. PhD thesis, Georgia Institute of Technology, 2005.
  • D. Kempe, P. Keskinocak, A. Kleywegt, S. Koenig, M. Lagoudakis, E. Markakis, A. Meyerson, C. Tovey, S. Jain. Auction-based Multi-robot Routing. Robotics:Science and Systems, pp. 343-350, 2005.
  • R. Lipton, E. Markakis, A. Mehta, N. Vishnoi. On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas. IEEE Conference on Computational Complexity (CCC 2005).
  • R. Lipton, E. Markakis, E. Mossel, A. Saberi. On Approximately Fair Allocations of Indivisible Goods. ACM Conference on Electronic Commerce, pp. 125-131, 2004.
  • R. Lipton, E. Markakis. Nash Equilibria via Polynomial Equations. LATIN 2004.
  • K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. V. Vazirani. Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP . Journal of the ACM, 50 (6), pp. 795--824, November 2003.
  • E. Markakis, A. Saberi. On the Core of the Multicommodity Flow Game. ACM Conference on Electronic Commerce, pp. 93-97, 2003. Recipient of the best student paper award. Invited for publication in special issue of Decision Support Systems.
  • R. Lipton, E. Markakis, A. Mehta. Playing Large Games using Simple Strategies. ACM Conference on Electronic Commerce, pp. 36-41, 2003.
  • M. Mahdian, E. Markakis, A. Saberi, V. V. Vazirani. A Greedy Facility Location Algorithm Analyzed using Dual Fitting. Proceedings of 5th International Workshop on Randomization and Approximation Techniques in Computer Science (APPROX-RANDOM), volume 2129 of Lecture Notes in Computer Science, pp. 127--137, 2001.
  • I. Kerenidis, E. Markakis, K. Potika, C. Siaterlis. MEDUSA: An Operating Systems Simulator. Internet- Education-Science, pp. 52-54, 2000.