EΘΝΙΚΟ ΚΑΙ ΚΑΠΟΔΙΣΤΡΙΑΚΟ ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΘΗΝΩΝ
ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ & ΤΗΛΕΠΙΚΟΙΝΩΝΙΩΝ

ΣΕΜΙΝΑΡΙΟ ΑΛΓΟΡΙΘΜΩΝ
Aκαδημαϊκό έτος 2007-08

Τo σεμινάριο Αλγορίθμων οργανώνεται από τον Τομέα Θεωρητικής Πληροφορικής και παρουσιάζει ερευνητικές δραστηριότητες στην περιοχή του σχεδιασμού και ανάλυσης αλγορίθμων και άλλων σχετικών θεματων. Μπορείτε να δείτε το πρόγραμμα των ετών 03-04, 04-05, 05-06 και 06-07. Για περισσότερες πληροφορίες απευθυνθείτε στον Καθηγητή Γιάννη Eμίρη.

Oι ομιλίες δίνονται (πλην εξαιρέσεων) στην Αίθουσα Τηλεσυσκέψεων, 2os όροφος, Kέντρο Δικτύων, στο Tμήμα Πληροφορικής & Tηλεπικοινωνιών, oπότε και μεταδίδονται σε πραγματικό χρόνο στο διαδίκτυο. Για οδηγίες σύγχρονης παρακολούθησης και παρακολούθησης των αποθηκευμένων video, δείτε http://mc.gunet.gr/hlive.html.  Φυσική πρόσβαση: με λεωφορείο ή μετρό-λεωφορείο.


ΠΡΟΓΡΑΜΜA

σε αντίστρoφη χρονολογική σειρά
(σε κίτρινο η αμέσως προσεχής ομιλία)
ΗΜΕΡΟΜΗΝΙΑ
ΟΜΙΛΗΤΗΣ
ΤΙΤΛΟΣ ΟΜΙΛΙΑΣ
Παρ. 6 Ιουνίου
12.00
Marco Antoniotti
(Dept Informatics, Systems & Communications, Universita` degli Studi di Milano Bicocca, Milan)
Models and Data in Systems Biology: Discovering Relations among Descriptions of Time-course Micro-array Experiments (abstract)
Τετ. 28 Μαϊου
11.00
Manuel Armada
(Vice Director, Ινστιτούτο Βιομηχανικού Αυτοματισμού, και Head of Automatic Control Dept, Instituto de Automatica Industrial (CSIC), Madrid)
Robotics at CSIC-Madrid: walking robots, control issues, software development (abstract)
Τετ. 7 Μαϊου
14.00
Γιάννης Βαλαβάνης (ΕΜΠ) Protein Sequence- and Structure-based Similarity Networks (abstract) (slides)
Tρίτη 6 Mαϊου, 13:00 George Zouridakis
(
Departments of Computer Science, Engineering Technology, and Electrical & Computer Engineering, University of Houston)
THE ROLE OF GAMMA BAND EEG ACTIVITY IN HUMAN LEARNING AND STRATEGY FORMULATION (abstract)
Παρασκ. 11 Απριλίου, 12.00
Michael Hemmer (MPI Saarbrucken, and U. Mainz)
New Algebraic Foundations for CGAL (abstract)
Πέμπτη 6 Δεκεμβρίου, 12:00 Alexander Okhotin
(Academy Research Fellow, Dept Math, U. Turku)
Boolean grammars as "better context-free grammars" (abstract)
Πέμπτη 22 Νοεμβρίου, 13.00
*** Γ31, Τμήμα Μαθηματικών ***
Bernd Sturmfels
(UC Berkeley and TU Berlin)
The Algebraic Degree of Semidefinite Programming (Abstract) (slides)
Πέμπτη 1 Νοεμβρίου
12.00
Ευριπίδης Μπάμπης
(U. Evry, Γαλλία)
Βελτιστοποίηση πολλαπλών κριτηρίων: Συμβιβασμός, Ειλικρίνεια, Συμμαχία και Δικαιοσύνη (doc)
Τρίτη 23 Οκτωβρίου 15.00
*** Aίθουσα Δ' ***
Δημήτριος M. Θηλυκός
(Τμήμα Μαθηματικών, ΕΚΠΑ)
Subexponential parameterized algorithms (Περίληψη: pdf, rtf)
Παρασκ. 19 Οκτωβρίου
14.00
Δημήτρης Αχλιόπτας
(UC Santa Cruz) 
Προβλήματα ικανοποίησης περιορισμών: από τη φυσική στους αλγορίθμους (Περίληψη) (Ομιλία)
Τρίτη 16 Οκτωβρίου, 11.00
*** Aίθουσα Δ' ***
Κωνσταντίνος Τσιρογιάννης
(ΠΜΣ Πληροφορικής & Τηλεπ/νιών) 
Παρουσίαση Διπλωματικής εργασίας: Διαγράμματα Voronoi στην βιβλιοθήκη CGAL (Περίληψη
Παρασκ. 12 Οκτωβρίου 13.00
*** Aίθουσα Δ' ***
Γρηγόρης Αλούπης
(Universite Libre de Bruxelles & Carleton University)
Διπλώνοντας και ξεδιπλώνοντας πολύεδρα (Περίληψη

ΠΕΡΙΛΗΨΕΙΣ ΟΜΙΛΙΩΝ


Παρ. 6 Ιουνίου, 12.00
Marco Antoniotti
(Department of Informatics, Systems and Communications, Universita` degli Studi di Milano Bicocca)
Models and Data in Systems Biology: Discovering Relations among Descriptions of Time-course Micro-array Experiments
The state-of-the-art approach in the interpretation of high-throughput experimental micro-array data is to perform some form of "clustering" and then compute a functional characterization via "enrichments" by categorical terms, e.g., by Gene Ontology (GO) terms. To provide further assistance in result interpretation, it may be useful to establish "relationships" among different clusters, especially in the case of time-course experiments.  This machine learning step is sometimes termed cluster meta-analysis, and several approaches have already been proposed to this end; such approaches usually rely on enrichments based on flat lists of GO terms.  However, GO terms are organized in three taxonomical graphs, whose structure should be taken into account when performing enrichment studies.

In order to tackle this problem, we have proposed a Kernel approach that can exploit such structured graphical nature, and we have
concentrated on its evaluation. We have then compared our approach against a specific flat list method by analyzing the alpha-subset of the well known Spellman's Yeast Cell Cycle data-set.

Using the Kernel method to perform the enrichment phase of the micro-array analysis is one of the building block of our work. Our
long term plan is to analyze time-course experiments by retrieving them or patching them together from the publicly available data bases, and by processing them with novel software tools, like GOALIE, which visualizes the relationships between clusters of closed-by time points. Such plan serves the overall goal to empower a biologist formulate temporally localized hypotheses about a phenomena evolution, in order to focus and expedite future experiments.

Τετ. 28 Μαϊου, 11.00
Manuel Armada (Vice Director, Ινστιτούτο Βιομηχανικού Αυτοματισμού, και Head of Automatic Control Dept, Instituto de Automatica Industrial (CSIC), Madrid)
Robotics at CSIC-Madrid: walking robots, control issues, software development

Topics: Short General presentation of CSIC - IAI. Presentation of work (projects) in the Institute,  relative to robotics. For example walking robots etc. Small presentation concerning control issues, with emphasis on their solutions (cards, software). We can also discuss with him solutions they have developed or used in the field of robotic platforms for manipulating or simulating human foot.

Ο Δρ. M. Armada είναι Vice Director στο Ινστιτούτο Βιομηχανικού αυτοματισμού του CSIC και Member of the Russian Academy of Natural Sciences. Eπίσης είναι Head of Automatic Control Department, Instituto de Automatica Industrial (CSIC), Madrid, SPAIN. Web:  http://www.iai.csic.es/dca.
CSIC is the largest public research body in with budget beyond 700ΜE. With centres throughout Spain, we play an active role in the scientific policy of all the country's autonomous regions. As a multidisciplinary body we cover all fields of knowledge, from basic research through to advanced technological development.
Τετ. 7 Μαϊου, 14.00
Γιάννης Βαλαβάνης (ΕΜΠ)
Protein Sequence- and Structure-based Similarity Networks

Network-based description has been widely used to describe complex systems that consist of elements with any type of interrelation. A set of proteins or folds is a complex system whose elements are interrelated on the concept of sequence- and structure-based similarity and can be described as a network. Here, several protein similarity networks constructed based on either sequence-derived features or structural alignment and a set of 311 proteins organized in class and fold level are presented. Network-topology measurements, like network degree, clustering coefficient, characteristic path length and vertex centrality, are utilized to characterize the networks. Sequence and structural similarity networks of proteins are found medium or highly interconnected due to continuous similarity transition during evolution, while the existence of both clusters and random edges classified their fully connected versions as Small World Networks. The study of similarity interrelations in the networks shows that α/β class contributes more than other classes to the interconnectivity found in structural and sequence space, while centrality measurements reveal certain folds which dominate network activity and function as hubs, e.g. the Globin-like and TIM-barrel folds. The proposed approach can serve as a platform for the development and optimization of sequence-based protein fold assignment methods directed by graph similarity metrics of networks that describe sequence and structural space.


Tρίτη 6 Mαϊου, 13:00
George Zouridakis (Departments of Computer Science, Engineering Technology, and Electrical & Computer Engineering, University of Houston)
THE ROLE OF GAMMA BAND EEG ACTIVITY IN HUMAN LEARNING AND STRATEGY FORMULATION
The significance of synchronous brain activity in complex cognitive processing has been the subject of several studies, which have shown
that cognitive states, such as perception, emerge from integrative brain processes that bind together different sensory inputs. This
study aims at developing computational tools to elucidate the role of synchronous brain activity in the process of human learning and
strategy formulation.
To this end, we recorded dense-array EEG and joystick data from human subjects while they performed a task with visuomotor and strategic
components. We developed rich visualizations of spatiotemporal profiles of brain activation based on coherence analysis of the EEG
recordings and their integration with the motor data. We found a strong relationship between spatiotemporal changes in brain activity
synchronization and level of performance on the task during various phases of learning.
More specifically, our study provides evidence for the presence of long-range synchronies in subjects who initially perform poorly and
later move to a significantly higher level of performance, while subjects who maintain a relatively consistent level of performance do
not exhibit this profile. These long range synchronies, which are present only in the gamma band and absent in lower frequencies,
suggest a tight cooperation between occipital and frontal brain regions in subjects who successfully undergo both phases of learning,
namely strategy formulation and strategy implementation.
Βιογραφικό:
George Zouridakis, Ph.D., is Associate Professor and Director of the Biomedical Imaging Lab at the University of Houston. He has been on the faculty of The University of Texas-Houston Medical School, where his clinical activities included Intraoperative Monitoring, Functional Brain Mapping, and Deep Brain Stimulation. His current research interests are in the areas of Biomedical Imaging, Computational Biomedicine, and Functional Brain Mapping. He is the main author of a book on Intraoperative Monitoring, CRC Press, 2001, and the Co-Editor-in-Chief of the "Handbook of Biomedical Technology and Devices", CRC Press, 2003. He has developed courses, given lectures, organized sessions at national and international conferences on Medical Imaging, and published more than 150 referred papers and abstracts. He is an Associate Editor of the IEEE Transactions on Biomedical Engineering and is also listed on Who’s Who in America.
Biomedical Imaging Lab, 713-743-8656, 713-743-1250  FAX, zouridakis@uh.edu, http://www.cs.uh.edu/~zouridakis

Παρασκ. 10 Απριλίου, 12.00
Michael Hemmer (MPI Saarbrucken, and U. Mainz)
New Algebraic Foundations for CGAL

CGAL is targeting towards exact computation with non-linear objects, in particular objects defined on algebraic curves and surfaces. As a consequence types representing polynomials, algebraic extensions and finite fields play a more important role in related implementations. The CGAL package Algebraic Foundations
has been introduced to stay abreast of these changes.

The package extends the former number type support of CGAL in the sense that it clearly  separates the algebraic structure from other characteristics of a type. In this way the framework is capable to support not only (real embeddable) number types but also other types such as complex numbers, polynomials, algebraic extension fields, and finite fields.  The package strictly follows the generic programming paradigm. Beside an introduction to generic programming, the talk will give an overview of the new Algebraic Foundations and the upcoming packages Modular Arithmetic and Polynomials.
 Πέμπτη 6 Δεκεμβρίου, 12:00
Alexander Okhotin (Academy Research Fellow, Department of Mathematics,University of Turku, Finland)
Boolean grammars as "better context-free grammars".
The basic model of syntax is a context-free grammar, which allows the use of a single logical connective: the disjunction. Boolean grammars complete the definition of a context-free grammar by including in the formalism of rules the missing Boolean operations: the conjunction and the negation. Their extended expressive power and the intuitive clarity of their descriptive means make them a more powerful tool for language specification than the context-free grammars. At the same time, the main context-free parsing algorithms, such as the Cocke-Kasami-Younger, the recursive descent and the generalized LR, can be extended to Boolean grammars without an increase in computational complexity, and have been implemented in software. These results will be surveyed in the talk, leading to the thesis of Boolean grammars' being "better context-free grammars". A list of most important open problems in the area will be given.

Σεμινάριο ΜΠΛΑ, από Κοινού με το Σεμινάριο του Τμήματος Μαθηματικών
Πέμπτη 22 Νοεμβρίου 13.00 *** Γ31, Τμήμα Μαθηματικών ***
Bernd Sturmfels (UC Berkeley and TU Berlin)
The Algebraic Degree of Semidefinite Programming

This lecture discusses recent interactions between convex optimization and algebraic geometry. Given a semidefinite programming problem which is specified by matrices over the rational numbers, each coordinate of its optimal solution is an algebraic number. We determine the degree of the minimal polynomials of these algebraic numbers. This degree measures the intrinsic algebraic complexity of solving semidefinite programs. Geometrically, it counts the critical points of a linear function over all matrices of fixed rank in a linear space of symmetric matrices.

Related paper here.


Παρασκ. 19 Οκτωβρίου
Δημήτρης Αχλιόπτας (UC Santa Cruz)
Προβλήματα ικανοποίησης περιορισμών: από τη φυσική στους αλγορίθμους

Πολλά NP-complete προβλήματα είναι εύκολα "κατά μέσο όρο". Για παράδειγμα, σε ένα τυχαίο γράφημα στο οποίο κάθε ακμή υπάρχει με πιθανότητα 1/2, μπορούμε να βρούμε κύκλο που να επισκέπτεται την κάθε κορυφή ακριβώς μία φορά (Hamilton cycle) σε γραμμικό χρόνο, κατά μέσο όρο. Από την άλλη, προβλήματα όπως η ικανοποιησιμότητα τυχαίων λογικών προτάσεων ή ο χρωματισμός τυχαίων γραφημάτων, φαίνεται να παραμένουν δύσκολα. Επιπλέον η δυσκολία αυτή μεγιστοποιείται γύρω από ένα κατώφλι πυκνότητας περιορισμών στο οποίο η πιθανότητα ύπαρξης λύσης πέφτει απότομα από σχεδόν 1 σε σχεδόν 0. Ο προσδιορισμός της θέσης αυτού του κατωφλίου για το κάθε πρόβλημα και η κατανόηση της συμπεριφοράς των αλγορίθμων κοντά του έχει προσελκύσει την προσοχή ερευνητών από επιστημονικές περιοχές όπως η τεχνητή νοημοσύνη, η θεωρητική πληροφορική, και η στατιστική φυσική.

Προκειμένου να κατανοήσουμε την πηγή της υπολογιστικής δυσκολίας, μελετούμε το πώς η γεωμετρία του συνόλου των λύσεων μεταβάλλεται καθώς προστίθενται περιορισμοί σε τέτοια προβλήματα. Αποδεικνύουμε ότι πολύ πριν οι λύσεις εξαφανιστούν, οργανώνονται σε ένα εκθετικό πλήθος από συστάδες (clusters), κάθε μια από τις οποίες είναι σχετικά μικρή και μακριά από όλες τις άλλες συστάδες. Επιπλέον, σε κάθε συστάδα η πλειονότητα των μεταβλητών είναι "παγωμένες", δηλαδή παίρνουν μόνο μία από όλες τις δυνατές τιμές της. Η ύπαρξη τέτοιων παγωμένων μεταβλητών δίναι μια διαισθητικά ικανοποιητική εξήγηση για τη δυσκολία που αντιμετωπίζουν οι περισσότεροι αλγόριθμοι στην εύρεση λύσεων σε τέτοια προβλήματα. Ταυτόχρονα, τα αποτελέσματά μας αποδεικνύουν τη μία από τις δύο βασικές εικασίες στις οποίες στηρίζεται η μέθοδος Survey Propagation, μια νέα αλγοριθμική τεχνική που εισήχθηκε πρόσφατα από τους φυσικούς και η οποία φαίνεται να έχει εξαιρετικές επιδόσεις στην επίλυση ορισμένων τυχαίων προβλημάτων ικανοποίησης περιορισμών.
 

Σύντομο βιογραφικό

Ο Δημήτρης Αχλιόπτας αποφοίτησε απο το τμήμα Μηχ. Η/Υ και Πληροφορικής του Πανεπιστημίου Πατρών το 1993 και έλαβε το Ph.D. του από το Πανεπιστήμιο του Τορόντο το 1999. Εργάστηκε στη Microsoft Research αρχικά σα μεταδιδακτορικός συνεργάτης και απο το 2000 ως ερευνητής. Από το 2005 είναι καθηγητής στο Πανεπιστήμιο της Καλιφόρνιας στη Santa Cruz. Τα επιστημονικά του
ενδιαφέροντα είναι επικεντρωμένα γύρω απο την αλληλεπίδραση της τυχαιότητας με τον υπολογισμό. Σχετικές εργασίες του έχουν παρουσιαστεί στα συνέδρια AAAI, FOCS, IJCAI, NIPS, PODS, SODA, STOC, καθώς και στα περιοδικά Annals of Mathematics, JACM, JAMS, και Nature. Το 2006 έλαβε το NSF CAREER award και το 2007 την Sloan Fellowship.



Τρίτη 16 Οκτωβρίου, 11.00 *** Aίθουσα Δ' **
Κωνσταντίνος Τσιρογιάννης (ΠΜΣ Πληροφορικής & Τηλεπ/νιών)
Παρουσίαση Διπλωματικής εργασίας: Διαγράμματα Voronoi στην βιβλιοθήκη CGAL

Εξετάζουμε το πρόβλημα της κατασκευής του 2Δ διαγράμματος Voronoi κύκλων. Αναλύεται η αρχική υλοποίηση του δυναμικού αλγορίθμου στην βιβλιοθήκη γεωμετρικών εφαρμογών CGAL. Προτείνεται μια νέα διάρθρωση της υλοποίησης που παρέχει την δυνατότητα της γενικότερης χρήσης των συστατικών στοιχείων του αλγορίθμου και από άλλες εφαρμογές. Παράλληλα παρουσιάζουμε την έννοια του
γεωμετρικού φιλτραρίσματος και την προσθήκη του στον αλγόριθμο κατασκευής του διαγράμματος. Γίνεται παρουσίαση των αποτελεσμάτων εκτεταμένων μετρήσεων επι της απόδοσης του αλγορίθμου εισαγωγής εστιών με την νέα διάρθρωση και σύγκριση με την απόδοση της αρχικής εκδοχής.



Παρασκ. 12 Οκτωβρίου, 13.00 *** Aίθουσα Δ' **
Γρηγόρης Αλούπης (Universite Libre de Bruxelles & Carleton University)
Διπλώνοντας και ξεδιπλώνοντας πολύεδρα

I will discuss certain results, old and new, from the topic of folding/unfolding polyhedra. The main focus is the following problem: We are given the surface of a convex polyhedron, and are allowed to cut along any of its edges as long as the resulting surface remains connected. We must keep each face rigid but may use the connecting edges as flexible joints. With an appropriate number of cuts, any given surface may be flattened onto the plane. However, is it possible to make the cuts in a way such that the flattened object does not self-overlap?