Elias Koutsoupias' weblog and personal page

Στο μεταπτυχιακό πρόγραμμα σπουδών του Τμήματος Πληροφορικής, έχει δρομολογηθεί η αλλαγή του προγράμματος σπουδών της 1η κατεύθυνσης. Αυτό απαιτεί τη συναίνεση του Τμήματος για την αλλαγή του πλαισίου (ΦΕΚ) που αφορά το πρόγραμμα σπουδών. Ελπίζω πως η αλλαγή θα γίνει σύντομα αφού όλοι φαίνεται να συμφωνούν σε αυτό. Αυτοί που θα εγγραφούν το 2007-8 στην πρώτη κατεύθυνση θα έχουν τη δυνατότητα να ακολουθήσουν το νέο πρόγραμμα στην ουσία. Τυπικά στην αρχή θα ακολουθούν το παλιότερο πρόγραμμα και θα μεταπηδήσουν στο νέο πρόγραμμα όταν ολοκληρωθεί η αλλαγή (έκδοση ΦΕΚ).

Η αναβάθμιση της πρώτης κατεύθυνσης του μεταπτυχιακού προγράμματος του Τμήματος Πληροφορικής και Τηλεπικοινωνιών έχει σκοπό τη βελτίωση και τον εκσυγχρονισμό του προγράμματος. Το σύνολο των βασικών μαθημάτων του νέου προγράμματος διαφέρει αρκετά από το προηγούμενο πρόγραμμα, αντιπροσωπεύει καλύτερα τις νέες τάσεις της Θεωρητικής Πληροφορικής και είναι σε αντιστοιχία με τα επιστημονικά ενδιαφέροντα των διδασκόντων.

Οι εμπλεκόμενοι καθηγητές προτείνουν η κατεύθυνση να έχει τον παρακάτω τίτλο και πρόγραμμα μαθημάτων.

Θεμελιώσεις και Εφαρμογές της Θεωρητικής Πληροφορικής

Βασικά Μαθήματα

1.  Αλγόριθμοι
2.  Υπολογιστική Πολυπλοκότητα
3.  Θεωρία Γλωσσών Προγραμματισμού 
4.  Υπολογιστική Γεωμετρία 
5.  Συνδυαστική Βελτιστοποίηση 
6.  Γραφικά, Οπτικοποίηση 
7.  Επιστημονικοί Υπολογισμοί 
8.  Παράλληλοι Αλγόριθμοι 
9.  Προσεγγιστικοί Αλγόριθμοι 
10.  Αλγοριθμική Θεωρία Παιγνίων 
11.  Κρυπτογραφία

Μαθήματα επιλογής

1.  Αλγόριθμοι στη Δομική Βιοπληροφορική
2.  Υπολογιστική Άλγεβρα
3.  Άμεσοι Αλγόριθμοι  
4.  Ειδικά Θέματα Θεωρητικής Πληροφορικής
• Αλγοριθμική Θεωρία Γράφων
• Πιθανοτικοί Αλγόριθμοι
• Γραμμικός και μη Γραμμικός Προγραμματισμός

2007.06.15-15:19.00
/Student Issues | 0 writebacks | permanent link

I gave a talk during the first Athens Colloquium on Algorithms and Complexity (ACAC 2006): On Mechanisms for Scheduling on Unrelated Machines.

Abstract: The mechanism design problem of scheduling tasks on n unrelated machines, in which the machines are the players of the mechanism, was proposed and studied in the seminal paper of Nisan and Ronen about ten years ago. It was shown there that the approximation ratio of mechanisms is between 2 and n. Despite the central role of the problem in the new area of Algorithmic Mechanism Design, there was no improvement on these bounds. In this talk, I will present some recent approaches and results.

2006.08.26-00:17.00
/Presentations | 0 writebacks | permanent link

With George Christodoulou and Angelina Vidali [CKV07], we improved the lower bound of the approximation ratio for the mechanism-design version of scheduling unrelated machines. The problem was proposed and studied in the 1998 seminal paper of Nisan and Ronen, where it was shown that the approximation ratio of mechanisms is between 2 and n, where n is the number of machines. Their paper brought to the attention of the CS theory community the notion of mechanism design and its algorithmic issues. Despite the central role of the scheduling problem in this area, there was no improvement since the original paper of Nisan and Ronen. We improved the lower bound from 2 to 2.41.

2006.08.25-12:09.00
/Research/Game Theory | 0 writebacks | permanent link

Για ποιους: Προπτυχιακούς φοιτητές κυρίως
Πότε: Δευτέρα 22/05/2006, 12:00-2:00
Πού: Αίθουσα Συνεδριάσεων (1ος όροφος)
Από ποιους: Κυρίως από φοιτητές που πέρασαν τη διαδικασία πρόσφατα.

Την Δευτέρα 22 Μαΐου στις 12:00 διοργανώνεται Ημερίδα Ενημέρωσης για Μεταπτυχιακά σε ΗΠΑ/Καναδά. Στην εκδήλωση θα μιλήσουν κυρίως φοιτητές που έχουν περάσει από αυτή την διαδικασία αιτήσεων και είτε ήδη σπουδάζουν σε κάποιο Πανεπιστήμιο στις ΗΠΑ ή τον Καναδά, είτε θα ξεκινήσουν το Φθινόπωρο τις σπουδές τους εκεί. Η εκδήλωση θα έχει περισσότερο χαρακτήρα συζήτησης μεταξύ φοιτητών. Θα πάρουν μέρος και κάποιοι καθηγητές με εμπειρία από Β. Αμερική.

Η εκδήλωση θα λάβει χώρα στην Αίθουσα Συνεδριάσεων του Τμήματος και θα διαρκέσει περίπου 2 ώρες. Το συνοδευτικό υλικό της Ημερίδας βρίσκεται ήδη σε ένα wiki που έχει δημιουργηθεί γι’ αυτόν τον σκοπό, το οποίο θα βελτιώνεται/ενημερώνεται συνεχώς, στην διεύθυνση: http://www.di.uoa.gr/~diwiki/

2006.05.15-23:21.00
/Student Issues | 4 writebacks | permanent link

I gave a talk at the Athens University of Economics and Business on Feb 2, 2006 on The price of anarchy of congestion games and mechanisms.

Abstract: Ideally, users who share the resources of a system should behave in a way that optimizes the performance of the system. But when users are selfish, they act in a way that optimizes their own individual and usually conflicting objectives. The price of anarchy is an attempt to measure the deterioration of the performance of a system due to selfish behavior of its users or components. I present recent results on the price of anarchy of congestion games.

When the price of anarchy is high, we want to redesign the game or the system to improve its performance. I present approaches such as mechanism design, taxes, and coordination mechanisms that attempt to improve the performance of systems with selfish users.

2006.02.03-08:34.00
/Presentations | 0 writebacks | permanent link

Τα άρθρα για τα μαθήματα δεν εμφανίζονται αυτόματα. Για να δείτε τα άρθρα για κάποιο μάθημα, επιλέξτε από το μενού Classes.

Αν χρησιμοποιειτε RSS για να δειτε τα αρθρα καποιας ταξης, επιλεξτε πρωτα απο το μενου την καταλληλη ταξη και μετα χρησιμοποιειστε το url απο το “Subscribe” στο δεξιο μερος. Π.χ. για την ταξη Game Theory το url ειναι
http://www.di.uoa.gr/~elias/index/Classes/Game%20Theory/index.html
ενω το RSS feed ειναι
http://www.di.uoa.gr/~elias/index/Classes/Game%20Theory/index.rss.

2005.02.22-12:05.00
| 0 writebacks | permanent link

This is my weblog and personal web page together. My main aim is to include information about my research and teaching at the University of Athens. Computer Science theorists do not seem to maintain weblogs (yet). I know only of Lance Fortnow’s weblog.

You can use the menu on the left to navigate and select topics. Especially for classes, the entries do not appear automatically. To see them, please select from the menu “Classes” or search.

The see only the entries in english click on the british flag on the upper-right corner. If you want to see all entries, you need to click on the greek flag .

You can subscribe to an RSS feed of this site, or even a feed of a topic. Select first the topic for the menu on the left—if you want all articles click on the top banner. Then use the subscribe link on the right side of the page or use the live bookmark features of your browser. For example to subscribe to all articles use this link
http://www.di.uoa.gr/~elias/index/index.rss?language=2
To subscribe to all articles about classes use this link
http://www.di.uoa.gr/~elias/index/Classes/index.rss?language=2

If you want to express your opinion about an article or to see the comments of others, please click on the writeback link at the end of the article. To avoid spam you have to verify that you belong to the homo sapiens spieces. Make sure that you verify this fact when you are asked to, otherwise your message will be lost.
Quiz: My method seems to defeat bots (at least for now). Can you see how?

The weblog is powered by blosxom, a cool perl script enhanced by scripts from the blosxom community.

2005.02.22-12:03.00
/About This Site | 1 writeback | permanent link

With George Christodoulou, we considered the price of anarchy of pure Nash equilibria in congestion games with linear latency functions. We showed that for general (asymmetric) games, the price of anarchy of maximum social cost is \Theta(\sqrt{N}), where N is the number of players. For all other cases of symmetric or asymmetric games and for both maximum and average social cost, the price of anarchy is 5/2.

The paper CK05 will appear in STOC 2005. Similar results, for the case of total latency cost function, were obtained by Awerbuch, Azar, and Epstein. Their paper will also appear in STOC 2005.

2005.02.14-15:33.00
/Research/Game Theory | 0 writebacks | permanent link

With George Christodoulou, we considered the price of stability, which is the optimistic price of anarchy (the ratio of the best equilibrium over the optimal allocation), for Nash and correlated equilibria. We showed that for linear congestion games the price of stability is between 1.577 and 1.6 for dominant strategies, Nash, and correlated equilibria. This holds for the average (sum) social cost. For the max social cost, the price of stability is \Theta(\sqrt{N}), where N is the number of players.

The results can be found in CK05b (submitted to ICALP’05). In the same paper, we extended some of the results of our STOC 05 (and also of the STOC’05 paper of Awerbuch, Azar, Epstein) to correlated equilibria.

2005.02.14-15:32.00
/Research/Game Theory | 0 writebacks | permanent link

Ο νέος θεσμός συμβούλου για τους φοιτητές του τμήματός μας μπορεί να λύσει πολλά προβλήματα αλλά για να πετύχει χρειάζεται τη συμμετοχή όλων, φοιτητών και συμβούλων. Είναι ευκαιρία τουλάχιστον σε αυτή τη φάση να καταγραφούν προβλήματα και προβληματισμοί αλλά και θετικές εμπειρίες. Κάποια από τα προβλήματα μπορεί να μην έχουν άμεση λύση ή να μην μπορούμε να τα λύσουμε καθόλου. Κάποια άλλα μπορεί να λυθούν άμεσα.

Από την άλλη, ίσως αυτή να είναι μια καλή ευκαιρία να δούμε κάποια θέματα πιο σφαιρικά και να διαλυθούν έτσι κάποιες λανθασμένες εντυπώσεις. Θα αναφερθώ σε 3-4 τέτοια θέματα που έτυχε να ακούσω.

See more ...

2004.12.16-07:25.00
/Student Issues | 8 writebacks | permanent link

An interesting book (in English) about mountainous Greece. Tim Salmon is a British teacher who has lived in Greece for many years and traveled a lot in the Agrafa region and around the vlach village of Samarina. He describes his encounters and, through them, he attempts to analyze the identity of modern Greece. Here is an extensive review.

2004.08.09-19:54.00
/Random Thoughts | 0 writebacks | permanent link

New York Times has an interesting collection of photos from Magnum Photos about the Olympics and Greece in general.

Since the subject is photos and Magnum, I should mention two collection of photos from Greece by the recently deceased Henri Cartier-Bresson: Greece 1953 and Greece 1961.

2004.08.06-16:41.00
/Random Thoughts | 0 writebacks | permanent link

A weblog is essentially an online diary. The author of the weblog posts articles called blogs on a web page. This is done usually in reverse chronological order.

Many weblog sites allow readers to write comments or replies on weblogs. These are called writebacks. You can read the writebacks to my postings or add a writeback by folowing the appropriate link at the end of my postings.

A similar concept is trackbacks. In this case readers post replies on their own weblog not on the original weblog. To connect a reply with the original weblog they leave a trackback. In other words, trackbacks are similar to short writebacks of the form “a reply to this blog has been posted on site …”.

As a weblog evolves, it is useful to have a fixed reference to each blog that does change over time. These are called permanent links.

2004.06.05-23:10.00
/About This Site | 0 writebacks | permanent link

Blosxom is a perl script for publishing weblogs. It is very extendable by many useful plugins written by the blosxom community —some of them employed in this website.

The author writes the weblongs as text or html files and blosxom creates the web pages automatically. One of its nice features is that the author can maintain the weblogs in a directory tree which reflects the categories or topics.

You can find more about blosxom on its website.

2004.06.05-22:56.00
/About This Site | 2 writebacks | permanent link

Here is a list of my publications from my old personal page—until I populate this weblog with references to these papers.

2004.05.11-10:09.00
/Research/Publications | 3 writebacks | permanent link

In a system with selfish users, the system may run at suboptimality. In CKN04, we propose coordination mechanisms as a way to improve the performance. Coordination mechanisms bring together online algorithms and the price of anarchy in a nice framework with challenging problems.

I also wrote a simple exposition article on the topic in the Bulletin of EATCS which I expanded for the SIGACT News.

2004.05.11-09:23.00
/Research/Game Theory | 0 writebacks | permanent link

The k-server problem is the central problem in the area of online algorithms. In my PhD thesis Kou94 and together with my friend and advisor Christos Papadimitriou KP95, we showed that the Work Function Algorithm has competitive ratio 2k-1; the previous bound, showed by Fiat-Rabani-Ravid and by Grove-Bartal, was exponential in k. Ten years later (as of this writing), the bound 2k-1 is still the best known. The k-server conjecture which states that there is a k-competitive algorithm remains the most challenging problem in the area of online algorithms.

I published a simpler proof of the 2k-1 bound in Kou99. I also published two more papers on the topic: in KP96 we proved the k-server conjecture for metric spaces of k+2 points and in BK04 we proved the conjecture for a few more special cases of metric spaces (line and weighted star).

2004.05.10-23:15.00
/Research/Online Algorithms | 3 writebacks | permanent link

In the paper KP99 with Christos Papadimitriou, we study the degradation in performance due to selfish behavior of the users. The paper is not technically deep but it raised an important question and had a huge impact. Together with a few other pioneering papers, such as Ronen and Nisan’s work on mechanism design, it opened up a beautiful new field in the intersection of Computer Science and Game Theory.

In this paper we view users as players in a non-cooperative game that play at the worst-case Nash equilibrium and compare with the optimal allocation. We initially called this the coordination ratio of the system (to relate it with the competitive ratio and approximation ratio); later Christos Papadimitriou called it the price of anarchy, and the latter term stuck.

In the paper we show that the price of anarchy for 2 facilities (machines, links) is exactly 3/2 and gave weak bounds for more facilities. In a later paper KMS03 with Marios Mavronikolas and Paul Spirakis, we showed tight bounds. Independently, Czumaj and Voecking proved a similar result but greatly expanded it to non-uniform facilities (see a nice review article by Czumaj).

2004.05.10-21:43.00
/Research/Game Theory | 1 writeback | permanent link

I discovered that RSS and news aggregators are cool ideas. I downloaded Freereader, a free aggregator for W2K.

Reuters now supports RSS. On its site there is a nice short explanation about RSS.

You can even subscribe to a syndicated feed of this weblog by clicking on the sidebar.

2004.04.28-18:27.00
/Random Thoughts | 0 writebacks | permanent link

This is my first weblog. I still don’t know my intended readership and for the moment I am writing it for myself alone.

2004.04.28-18:27.00
/Random Thoughts | 4 writebacks | permanent link