I am a professor at the University of Athens. My research interests are in Theoretical Computer Science and include algorithmic game theory, its applications to the internet and the web, online algorithms, and more-generally decision-making under uncertainty.
I got my undergraduate degree from the National Technical University of Athens and my PhD in Computer Science from the University of California in San Diego (UCSD), in 1994. The next 7-8 years I was assistant and associate professor at the University of California at Los Angeles (UCLA). Since 2001, I have been a professor at the University of Athens.
I am in the program committees of ICALP 2010 (track A), EC 2010, and SIROCCO 2010. I am also in the editorial board of the Journal of Computer and System Sciences (JCSS).Publications
At last, I proceeded to publish in a journal (CS Review) the paper of STACS 1999 which introduced the notion of price of anarchy (co-authored with Christos Papadimitriou). At the time, we called it "coordination ratio", but later Christos coined the catchy term "price of anarchy". Nobody could predict the impact of this work---including, of course, the committee which rejected it from a conference. Ten years later, it has more than 700 references to it, according to scholar.google.
In ESA 2009, with George Christodoulou and Paul Spirakis, we study how much the price of anarchy and the price of stability change when we consider approximate equilibria. We got almost tight results, as functions of the approximation ratio, for both atomic and non-atomic games, generalizing the existing results on exact equilibria. Surprisingly, we used a common approach for both atomic and non-atomic games.
The volume of CS Review which includes the STACS 1999 paper on the price of anarchy consists of a collection of articles to honor Christos Papadimitriou. My contribution was a review article for the k-server problem.
My recent research activity in online algorithms is focused on streaming algorithms. With Luca Becchetti we used competitive analysis to study a simple problem in streaming computing: how to maintain a maximum or almost maximum element of a sliding window with limited memory. Our main result is a surprising low competitive ratio for the aggregate maximum. More precisely when the algorithm has limited memory $k$ and the objective is the sum of the maximum values in memory, the competitive ratio is $1+\Theta(1/k)$. This ratio is both against offline algorithms with the same limitations in memory and against offline algorithms with unlimited memory.
A detailed list of my publications can be found by following the link Publications.
Talks
Some of my recent presentations and lectures are:- Mechanism design for scheduling unrelated machines
- A lecture I gave at the AEOLUS school in Paderborn in April 2008.
- Game-theoretic mechanisms
- An extended lecture I gave at the DYNAMO school in Reykjavik in July 2008.
- Competitive analysis of aggregate max in windowed streaming
- A presentation in ICALP, Rhodes, July 2009.
- Approximate Price of Anarchy and Stability
- An invited talk in SAGT, Paphos, October 2009.
- Approximate Price of Anarchy and Stability
- A slightly different version presented in a workshop at CRM, Barcelona, November 2009.
Courses
The fall semester of the academic year 2009-10, I teach the courses
- Math 4 CS
- A course undergraduate students.
- Algorithms
- A course for graduate and advanced undergraduate students which covers the fundamentals of algorithmic design and analysis.
- Online Algorithms
- A course for graduate students which addresses the most central issues of online algorithms.
You can find more information about these courses—and about courses of past years—by following the link Courses.
For students
If you want a recommendation letter, or you are interested in an undergraduate or MS thesis, please make sure you follow these instructions.I didn't move everything from my old web page to this one. You can still access it.