Oι ομιλίες δίνονται στο Tμήμα Πληροφορικής & Tηλεπικοινωνιών. Πρόσβαση: με λεωφορείο ή μετρό-λεωφορείο.

Many NP-complete problems are easy for random inputs. For example, in a random graph where each edge is present with probability 1/2 one can find a Hamiltonian cycle in linear expected time. On the other hand, random instances of problems such as satisfiability and graph coloring appear to be hard. Moreover, experimentally, they appear to be hardest near their "threshold", a constraint density where the probability of a random instance having a solution drops rapidly from near 1 to near 0.

I will discuss a new approach for locating such thresholds, based on the so-called "second moment method". The basic idea is to track the geometry of the set of solutions of a problem, as constraints are added. This allows us not only to locate thresholds but, further, to get rigorous insight on why many algorithms have a hard time near them. Moreover, we will see that combining some of these insights with heuristic ideas from physics motivates an exciting new class of algorithms for constraint satisfaction problems.

Η ομιλία θα μεταδοθεί σε πραγματικό χρόνο στο διαδίκτυο. Για τον αντίστοιχο σύνδεσμο και οδηγίες χρήσης, δείτε http://lessons.di.uoa.gr/mediacenter.php.

Ορίζουμε και μελετάμε δύο προβλήματα βελτιστοποίησης της χρήσης των διαθέσιμων πόρων σε πλήρως οπτικά δίκτυα πολλαπλών ινών που χρησιμοποιούν τεχνολογία WDM:

- Ελαχιστοποίηση κόστους οπτικών ινών: δίνεται το πλήθος των διαθεσίμων μηκών κύματος ανά οπτική ίνα και ζητείται η ελαχιστοποίηση του κόστους των οπτικών ινών που χρειάζεται να δεσμευθούν προκειμένου να εξυπηρετηθεί ένα σύνολο αιτήσεων επικοινωνίας.

- Ελαχιστοποίηση πλήθους μηκών κύματος: δίνεται το πλήθος των διαθέσιμων παράλληλων ινών σε κάθε οπτικό σύνδεσμο και ζητείται να βρεθεί το ελάχιστο πλήθος μηκών κύματος που αρκούν για να εξυπηρετηθεί ένα σύνολο αιτήσεων επικοινωνίας.

Διατυπώνουμε τα παραπάνω προβλήματα ως προβλήματα εύρεσης και χρωματισμού μονοπατιών σε γράφους και για το καθένα από αυτά εξετάζουμε δύο εκδοχές: την μη κατευθυνόμενη, που αντιστοιχεί σε αμφίδρομη (full-duplex)  επικοινωνία, και την κατευθυνόμενη, που αντιστοιχεί σε μονόδρομη (one-way) επικοινωνία.  Επιπλέον, για κυκλικές τοπολογίες εξετάζουμε και την περίπτωση όπου η δρομολόγηση είναι προκαθορισμένη. Παρουσιάζουμε αλγορίθμους πολυωνυμικού χρόνου που δίνουν ακριβείς ή προσεγγιστικές λύσεις σταθερού παράγοντα για τοπολογίες αλυσίδας (chain), δακτυλίου (ring), αστέρα (star), αράχνης (spider)  και δένδρου (tree).

(Τα αποτελέσματα που παρουσιάζονται προέκυψαν σε συνεργασία με τους: Ε. Ζάχο, Χ. Νομικό, Κ. Ποτίκα, T. Erlebach, και Σ. Στεφανάκο.)

Η ομιλία θα μεταδοθεί σε πραγματικό χρόνο στο διαδίκτυο. Για τον αντίστοιχο σύνδεσμο και οδηγίες χρήσης, δείτε http://lessons.di.uoa.gr/mediacenter.php.

Στην ομιλία αυτή, θα παρουσιάσουμε τους γράφους αλληλεπιδράσεων, ένα νέο μοντόλο για το πρόβλημα της εγωιστικής χρονοδρομολόγησης, όπου οι χρήστες υπόκεινται σε περιορισμούς τοπικότητας. Μέσα στο νέο μοντέλο, τίθεται εύλογα η ερώτηση χαρακτηρισμού του καλύτερου ή χειρότερου γράφου ως προς μία δεδομένη ισορροπία Nash. Μέχρι τώρα, έχουμε μόνο απαντήσει το αντίστροφο ερώτημα: για δεδομένο γράφο (τον γράφο
των παραλλήλων συνδέσμων), ποια είναι η καλύτεη ή η χειρότερη ισορροπία Nash; Θα δώσουμε μερικές απαντήσεις για τη νέα ερώτηση στην ειδική περίπτωση των κυβικών γράφων. Θα συζητήσουμε επίσης διάφορες τοπολογικές και αλγεβρικές συνθήκες για την μοναδικότητα (ή μη) της πλήρως μικτής ισορροπίας Nash.

(Αυτή είναι κοινή δουλειά με τους Robert Elsasser, Martin Gairing, Thomas Lucking και Burkhard Monien.)

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

Περίληψη της ομιλίας σε video (video).

Η ομιλία θα μεταδοθεί σε πραγματικό χρόνο στο URL: rtsp://vod.grnet.gr/broadcast/semin.rm. Για οδηγίες σχετικά με την παρακολούθηση, δείτε http://lessons.di.uoa.gr/mediacenter.php.

Solving polynomial equations is ubiquitous in many domains: computer aided geometric design, robotics, computer vision, signal processing. More specifically, in geometric problems, solving polynomial equations
appears as a fundamental ingredient, used as a black box in many algorithms.

In this presentation, we will describe such problems which requires intensive resolution of polynomial equations. We will first consider problems which require the treatment of algebraic numbers, such as computing the arrangement of curves and surfaces and show how dedicated methods can be devised for the sake of efficiency and robustness. In shape analysis, topology computation, meshing algorithms, solving polynomial equations is also a critical part. We will illustrate this remark, by descriptions of methods for meshing implicit surfaces and some experimentations.

Often, polynomial systems depending on parameters are present in these applications. Such systems are usually coming "in families", sharing the "same shape" but with different values of the parameters. Their resolution need to be efficient and robust. We will show how resultant-based methods allows us to implement preprocessing steps which leads to solvers adapted to such families of systems. This will be illustrated on a geometric interpolation
problem, namely the computation of cylinders through a cloud of points.

The localization of the solutions is also another question, which has to be addressed in geometric computation. Indeed, we are often interested in a subset of all the solutions of a system. We will show how methods based
on Bernstein polynomial representation allow us to handle this question. A method combining symbolic and numeric techniques will be described and illustrated by a comparison with algebraic techniques, in geometric problems, such as computing the self-intersecting points of parameterized surfaces.