Oι ομιλίες δίνονται στην Αίθουσα Δ' του Tμήματος Πληροφορικής & Tηλεπικοινωνιών (εκτός εξαιρέσεων). Πρόσβαση: με λεωφορείο ή μετρό-λεωφορείο.

Μετά μια συνοπτική εισαγωγή, όπου αναδεικνύεται η σημασία γεννητριών ισχυρών ψευδοτυχαίων αριθμών για τη διαχείριση ασφαλείας υπολογιστικών και επικοινωνιακών συστημάτων, η παρουσίαση εστιάζει στις ακόλουθες ερευνητικές προσπάθειες:
1. Στον προσδιορισμό και την αξιοποίηση νέων πηγών τυχαιότητας ως βάσεων γεννητριών ακολουθιών ψευδοτυχαίων αριθμών, αλλά και για την ενδυνάμωση υφισταμένων γεννητριών. Οι μέθοδοι αυτές βασίζονται σε διάφορες τεχνικές νευρωνικών δικτύων, όπως feed-forward Artificial Neural Networks του τύπου MultiLayer Perceptron (MLP).
2. Στην ανάπτυξη ενός test για την αξιολόγηση της μη προβλεψιμότητας γεννητριών (ψευδο-)τυχαίων ακολουθιών, το οποίο βασίζεται επίσης στις ανωτέρω τεχνικές νευρωνικών δικτύων.
3. Στην εφαρμογή του test αυτού, καθώς και άλλων γνωστών στατιστικών δοκιμών για την αξιολόγηση της ποιότητας των προτεινόμενων γεννητριών. 

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

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

Η γραμμική πολυπλοκότητα αποτελεί σημαντικό κριτήριο ανθεκτικότητας ακολουθιών σε αλγορίθμους κρυπτανάλυσης, όπως ο αλγόριθμος των Berlekamp-Massey. Παρουσιάζονται μέθοδοι προσδιορισμού της αναπαράστασης ίχνους (ισοδύναμα των συντελεστών του Διακριτού Μετασχηματισμού Fourier) των παραγόμενων ακολουθιών για δοθέν μη-γραμμικό φίλτρο. Αντιστρόφως, προτείνονται τρόποι εύρεσης μη-γραμμικών φίλτρων που παράγουν ακολουθίες καθορισμένης γραμμικής πολυπλοκότητας.

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

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

Τέλος, παρουσιάζεται η δημιουργία ακολουθιών που επιδεικνύουν τα χαρακτηριστικά λευκού θορύβου ανωτέρας τάξης και παράγονται από καταλλήλως επιλεγμένα ζεύγη ακολουθιών της ιδίας ή διαφορετικών ελαχίστων περιόδων. Δίνονται αποτελέσματα που αφορούν τις ακολουθίες τύπου Gold, δυϊκές BCH και παράγωγα αυτών, ενώ παρουσιάζεται μία νέα κλάση ακολουθιών, οι KRG. Η ποιότητα των ανωτέρω ακολουθιών αποδείχθηκε με πειράματα προσομοίωσης σε ταυτοποίηση διγραμμικών συστημάτων. 

Οι τεχνολογίες κινητού κώδικα και κινητών πρακτόρων, επεκτείνουν τις δυνατότητες απομακρυσμένης εκτέλεσης και υπολογισμού σε κατανεμημένα περιβάλλοντα και ανοικτά δίκτυα, όπως είναι το διαδίκτυο. Όμως, οι τεχνολογίες αυτές εισάγουν νέες απειλές ασφάλειας. Σκοπός της ομιλίας είναι η ταξινόμηση των προβλημάτων ασφάλειας της τεχνολογίας κινητού κώδικα και κινητού πράκτορα , και η παρουσίαση διαφόρων κρυπτογραφικών πρωτοκόλλων, αρχιτεκτονικών και μηχανισμών ασφάλειας που μπορούν να χρησιμοποιηθούν για την αντιμετώπιση αυτών των προβλημάτων. Τέλος, εξετάζονται ανοικτά ερευνητικά πεδία στην ασφάλεια αυτών των τεχνολογιών.

Στο πρώτο μέρος της διάλεξης κάνουμε μια ολική παρουσίαση της μεθόδου παραγοντοποίησης μέσω των ελλειπτικών καμπυλών, εξετάζοντας όλες τις περιπτώσεις στο κλασικό και πεπερασμένο επίπεδο. Μετά την παρατήρηση του Lagrange, παρουσιάζόυμε το θεώρημα του Hasse και αναλύουμε με παραδείγματα την εφαρμογή της μεθόδου του Lenstra και τα καλύτερα αποτελέσματα των Curry, Lygeros & Mizony, Izumi, Dodson και Backstrom.

Στο δεύτερο μέρος μελετούμε τις ειδικές και τις γενικές επιθέσεις των κρυπτοσυστημάτων του τύπου Diffie και Hellman που βασίζονται στις επιλύσεις των προβλημάτων IFP, DLP και ECDLP έτσι ώστε να εντοπίσουμε τους κινδύνους όσον αφορά την ασφάλεια της κρυπτογράφισης ειδικά για το πρόβλημα του διακριτού λογάριθμου των ελλειπτικών καμπυλών με την ρ-μέθοδο του Pollard.

The raw data obtained at the acquisition stage of the graphics pipeline are often described by 3D point clouds. Nevertheless, most of the geometry processing algorithms, e.g. simplification, parameterization, smoothing, as well as most of the rendering algorithms, require some extra topological information, usually in the form of triangle mesh connectivity. Surface reconstruction is the problem of modeling a 3D point cloud with a triangle mesh.

We present a Learning algorithm for surface reconstruction simulating an incrementally expanding neural network known in the literature as Growing Cell Structure. The neural network learns the geometry of the point cloud through a competitive learning process, expands by splitting its most active vertices, and improves its connectivity by removing the least active vertices. The topology is learned through statistics based operators which create boundaries and merge them to create handles.

http://www.mpi-sb.mpg.de/~ivrissim/learning.html

While privacy is an undeniable right of law-abiding citizens, a functional society must also offer effective mechanisms for monitoring abuse and tracing of entities or actions that deviate from established policies. Entity identification and traceability of actions are crucial components of an electronic transaction system that is robust against adversaries that attempt to subvert it or engage in illegal activity. This apparent necessity for wide deployment of electronic identification and traceability raises serious privacy concerns. Indeed, the power of digital data processing allows rapid and inexpensive aggregation of private data. Moreover, the value of personal information in electronic form motivates abuse on the side of service providers as well as it makes service provider's databases a prized hacking target. This new potential of large-scale abuse of private data leads privacy advocates to demand anonymity in electronic transaction systems. In the other end, service providers and law-enforcement entities require strong identification and traceability to prevent malicious activities. In this tug of war cryptography comes to the rescue. This talk will deal with a new cryptographic tool, called "Traceable Signatures" as well as other related cryptographic primitives that allow the effective balancing of privacy and traceability in electronic transaction systems.

related papers:
* "Traceable Signatures" (A. Kiayias, Y. Tsiounis, M. Yung) EUROCRYPT 2004. http://eprint.iacr.org/2004/007
* "Anonymous Identification in Ad-Hoc Groups" (Y. Dodis, A. Kiayias, A. Nicolosi, V. Shoup) EUROCRYPT 2004.

CGAL (http://www.cgal.org) is an academic software project started 8 years ago with the goal to make "a large body of geometric algorithms, from the field of Computational Geometry, available to industrial applications". I will present the different aspects of this open source project : its current status, how it is organized, how it evolves, what functionalities the library provides, and some of the key software design issues behind it.

Exploitation and processing of images and visual information is an increasing domain of study in the areas of computer science, applied mathematics, engineering, psychology, etc. Most particular, medical image analysis is the most well established application domain. Automated extraction of anatomic structures from different image modalities is an important tool for diagnosis.

In this talk, we address the segmentation of the left ventricle in echocardiographic images, a task with important computer aided diagnosis value. A model-based variational framework is considered that aims at extracting the left ventricle at each frame of the cardiac cycle. The approach consists of three stages. Modeling, detection and local segmentation refinements. Towards robust solution, the problem is considered in the temporal domain and solutions at each frame are constrained to be consistent. Promising results demonstrate the potentials of the proposed framework.

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

Πρόσφατες έρευνες ενισχύουν την άποψη ότι, παρόλο που είναι αρκετά φιλόδοξο ως σχέδιο, είναι δυνατόν να οριστεί και να υλοποιηθεί ένα γενικό πλαίσιο, με τη χρήση του οποίου να γίνεται δυνατή η αναπαράσταση με τυπικό τρόπο πολύπλοκων προτάσεων και των αποδείξεών τους σε γλώσσες χαμηλού επιπέδου (ενδιάμεσες ή συμβολικές) με ισχυρά συστήματα τύπων. Σε μια τέτοια γλώσσα, ένα αρχείο πιστοποιημένου κώδικα είναι απλά ένα πρόγραμμα, του οποίου ο τύπος παρέχει μια συλλογή από ιδιότητες που το πρόγραμμα ικανοποιεί.  Ο ελεγκτής τύπων της γλώσσας μπορεί στατικά και σχετικά εύκολα να αποκρίνεται για το αν ένα δεδομένο αρχείο είναι συνεπές και, στην περίπτωση που είναι, το πρόγραμμα μπορεί εν συνεχεία να εκτελεστεί χωρίς επιπλέον επιβάρυνση στην απόδοση.

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

Techniques for Accelerating and Enhancing the Rendering of Virtual RealityEnvironments.

This presentation aims to describe the methodological aspects of the adaptation of various established graphics and 3D game techniques, in order to visually enrich and extend the common capabilities of virtual environment visualization platforms. These techniques will be briefly described and the various practical implementation issues and problems will be discussed. Examples and application case studies from the research and ongoing VR productions of the VR department of the Foundation of the Hellenic World, in
order to demonstrate the enhancements described.

Θεωρούμε το πρόβλημα του υπολογισμού των συνεκτικών συνιστωσών (connected components) του συμπληρώματος δοθέντος γραφήματος. (Οι συνεκτικές συνιστώσες ενός μη κατευθυνόμενου γραφήματος G είναι τα σύνολα της διαμέρισης του συνόλου κόμβων του G όπου δύο κόμβοι ανήκουν στο ίδιο σύνολο αν και μόνον αν υπάρχει διαδρομή στο G από τον έναν στον άλλον.)

Το παραπάνω πρόβλημα μπορεί να επιλυθεί με υπολογισμό του συμπληρώματος και εφαρμογή σε αυτό κάποιου αλγορίθμου για τον υπολογισμό συνεκτικών συνιστωσών.  Ωστόσο, μια τέτοια προσέγγιση γενικά οδηγεί σε μη βελτιστη λύση (από άποψη χρόνου υπολογισμού), όπως π.χ. στην περίπτωση των αραιών γραφημάτων. Αν και για το πρόβλημα που μελετάμε έχουν προταθεί βέλτιστοι ακολουθιακοί αλγόριθμοι, αυτοί βασίζονται σε αναζήτηση κατά βάθος (DFS) ή αναζήτηση κατά πλάτος (BFS) και συνεπώς δεν επιδέχονται αποτελεσματικό παραλληλισμό.

Στην παρούσα ομιλία, θα περιγράψουμε έναν απλό παράλληλο αλγόριθμο για τον υπολογισμό των συνεκτικών συνιστωσών του συμπληρώματος ενός γραφήματος με n κόμβους και m ακμές ο οποίος εκτελείται σε O(log n) χρόνο και απαιτεί O((n+m) / log n) επεξεργαστές στο μοντέλο EREW PRAM. Ο αλγόριθμος βρίσκει εφαρμογές σε διάφορα προβλήματα και μπορεί να βοηθήσει στην κατασκευή αποτελεσματικών παράλληλων αλγορίθμων για αυτά.  Για παράδειγμα, για το πρόβλημα της αναγνώρισης ασθενώς τριγωνικών γραφημάτων (weakly triangulated graphs) επιτυγχάνουμε έναν αλγόριθμο O(log^2 n)-χρόνου και O((n+m^2) / log n)-επεξεργαστών στο μοντέλο EREW PRAM.

Τα αποτελέσματα που παρουσιάζονται στην ομιλία προέκυψαν σε συνεργασία με τους  Ka Wong Chong (The University of Hong-Kong) και  Σταύρο Νικολόπουλο (Πανεπιστήμιο Ιωαννίνων).

Το θέμα της ομιλίας είναι τα παίγνια ανίχνευσης και κατάκτησης σε γραφήματα. Σε τέτοια παίγνια, ο στόχος είναι η συστηματική μετακίνηση ενός συνόλου ανιχνευτών στους κόμβους και τις ακμές ενός γραφήματος με σκοπό την σύλληψη ενός «σοφού» και «ταχύτατου» φυγά ο οποίος κρύβεται μέσα σε αυτό. Βασική εφαμογή του παραπάνω μοντέλου είναι το πρόβλημα του καθαρισμού ενός δικτύου από προγράμματα τα οποία ενεργούν κακοβούλως ως ωτακουστές ή ως ιοί. Περιγράφουμε την υπολογιστική πολυπλοκότητα αυτών των παιχνιδιών και την σχέση τους με μια σειρά σημαντικών γραφοθεωρητικών παραμέτρων. Συγκεκριμένα αντιμετωπίζουμε το παρακάτω ερώτημα, γνωστό και ως «ερώτημα
της επαναμόλυνσης»:

Είναι δυνατόν να ανιχνεύσουμε ένα γράφημα χρησιμοποιώντας λιγότερους ανιχνευτές εάν επιτρέψουμε «επαναμόλυνση», δηλ., αν επιτρέψουμε στο φυγά να επισκεφτεί τοποθεσίες που έχουν ήδη ανιχνευτεί;» Παρουσιάζουμε ένα γενικό δομικό θεώρημα που παρέχει συνθήκες ικανές για μια αρνητική απάντηση στο παραπάνω ερώτημα και θα σχολιάζουμε τις επιπτώσεις του και τις εφαρμογές του.

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

Πέμ. 23 Οκτωβρίου, 2.00 μμ
Μενέλαος Καραβέλας (University of Notre Dame, Indiana)
Roots of polynomials: computation and representation

As computational geometry moves towards curved and/or moving objects, the need to perform basic arithmetic operations on such objects in a robust and efficient manner becomes increasingly important. Such a need, for example, becomes apparent when we consider arrangements of conic arcs or the Voronoi diagram for circles. The predicates involved in such algorithms require the comparison of real roots of polynomials of low degree, or even the representation of such roots.

An even more demanding case is that of kinetic data structures, a framework that deals with geometric structures whose defining objects are in motion. In kinetic simulations, the geometric objects typically move along polynomial trajectories, and the critical events of the simulation are the times when the geometric predicates fail. These critical events are, for most of the interesting geometric structures, real roots of polynomial functions, whose variable represents time.

In this talk we discuss how to compute and represent real roots of polynomials. Our approach is based on Sturm sequence theory. We are interested in balancing three, fairly opposing, considerations: exactness, robustness and efficiency. Exactness has to do with producing the correct output, for example, correctly comparing the roots of two polynomials. Robustness refers to handling correctly both generic and degenerate input (in this context a polynomial with multiple real roots is considered degenerate). Efficiency is dealt with by using filtering techniques, which enable us to perform computations very quickly away from degeneracies (with a small overhead), and which pose interesting design questions on how to implement our approach.