Τρίτη 24.06.2010, 2μμ

Tuesday 24.06.2010, 2pm

Polynomial Interpolation of Cryptographic Functions

(Πολυωνυμική παρεμβολή κρυπτογραφικών συναρτήσεων)

[watch video!]

Gerasimos C. Meletiou

(TEI of Epiros)

Abstract. This talk will discuss the discrete logarithm and Diffie Hellamn problems and overview algorithms that utilize polynomial interpolation for solving them. More details follow in Greek.

Στην παρουσίαση αυτή θα γίνει αρχικά σύντομη αναδρομή στις συναρτήσεις του Διακριτού Λογαρίθμου και Diffie – Hellman και στις εφαρμογές τους στην Κρυπτογραφία, καθώς και στις πρώτες προσπάθειες χρήσης της παρεμβολής κατά Lagrange για τον υπολογισμό τους.

Στη συνέχεια θα παρουσιαστούν αποτελέσματα που αφορούν στον προσδιορισμό κατωτέρων ορίων (Lower Bounds) για τον βαθμό και την sparcity των πολυωνύμων που παρεμβάλουν τις κρυπτογραφικές συναρτήσεις. Τέλος θα παρουσιαστεί η συνάρτηση του Διπλού Διακριτού Λογαρίθμου και της ρίζας του Διακριτού Λογαρίθμου και οι εφαρμογές τους, καθώς και αποτελέσματα σχετικά με τη χρήση παρεμβολής για τον υπολογισμό τους και εύρεσης κατωτέρων ορίων.

Τρίτη 25.05.2010, 3μμ

Tuesday 25.05.2010, 3pm

Lattices and Fully Homomorphic Encryption (3/3)

Christos LItsas

(University of Athens - MPLA)

Abstract. This is a presentation of the recent result of C. Gentry on Fully homomorphic encryption based on ideal lattices.

Παρασκευή 23.04.2010, 3μμ

Friday 23.04.2010, 3pm

Multivariate (aggregate) separation bounds

Elias Tsigaridas

(University of Aarhus)

Abstract. We present new and close to optimal separation bounds, that is bounds on the minimum distance between any two isolated roots of a polynomial system. We call them DMM after Davenport, Mahler and Mignotte. These are the first bounds applicable to arbitrary positive dimensional systems. For the construction we exploit the structure of the system and the height of the sparse resultant by means of mixed volume, as well as recent advances on aggregate root bounds for univariate polynomials. DMM allows us compute improved bounds for the number of steps that a subdivision algorithm performs in any dimension.

This is joint work with Ioannis Emiris and Bernard Mourrain.

Πέμπτη 15.04.2010, 3μμ

Thursday 15.04.2010, 3pm

Γεωμετρική Μοντελοποίηση και Eισαγωγή στο λογισμικό Axel

[video]

Angelos Mantzaflaris

(INRIA Sophia-Antipolis και ΕΚΠΑ)

Abstract. We give an introduction to the Axel geometric-modeling environment(http://axel.inria.fr), developed at INRIA, France. Axel is open-source software which aims at porting state-of-the-art

computational algebra tools to CAD technology. Using simple OpenGL primitives such as points, lines or triangles, Axel (a QT-based application) effectively visualizes and manipulates point clouds,

meshes, parametric and implicit curves/surfaces or volumes. The computational support behind Axel is embedded in several C++ libraries of the Mathemagix project (www.mathemagix.org), which bring advanced algorithms of computational algebra to the frame of geometric modeling. This includes effective algebraic representations, multivariate polynomial solvers, certified local computations, treatment of singular cases.

The main tasks supported by Axel include computing the topology of algebraic curves, the arrangement of several algebraic curves, the topology of surfaces, the (self-)intersection of parametric surfaces. A way to extend or add functionalities is the plugin system. Among currently available plugins we find a plugin for 3D polytopes, an algebraic singularity analysis plugin, isogeometic analysis plugins, a tree reconstruction plugin and GPU ray caster plugin.

Whoever is interested may bring his/her Linux machine and shall have Axel installed with our help, around 20 minutes before the beginning of the talk, so as to follow the demos of the talk. A VirtualBox environment shall be available for Windows users.

Τετάρτη 24.03.2010, 1μμ

Wednesday 24.03.2010, 1pm

Unique-maximum and conflict-free vertex colorings of graphs

Panagiotis Cheilaris

(Center for Advanced Studies in Mathematics Ben-Gurion University)

Abstract. Vertex colorings of graphs is an active research area with many practical applications in fields like operations research  (e.g., scheduling) and computer science (e.g., register allocation),

but also many theoretical challenges and open problems. We consider unique-maximum and conflict-free vertex colorings of graphs which are stronger versions of traditional vertex coloring. These two colorings have applications in:

* efficient solving of sparse linear systems of equations,

* scheduling parallel assembly of products,

* finding local optima in neighborhood structures,

* frequency assignment in cellular, wireless, and sensor networks.

A unique-maximum coloring of a graph G is an assignment of colors (i.e., positive integers) to the vertices of G such that in every simple path p of G the maximum color that occurs in p, occurs

exactly one time in p. In a conflict-free coloring of G, in every simple path p of G, there must be a color that occurs exactly one time in p (not necessarily the maximum one in p).

We present results on the computational complexity of the above colorings and we investigate the relationship between the two colorings. We introduce games on graphs that are closely related

to the above colorings and prove lower and upper bounds on the optimal number of colors of a unique-maximum and a conflict-free coloring for some families of graphs.

Joint work with Géza Tóth.

Τετάρτη 10.03.2010, 1μμ

Wednesday 10.03.2010, 1pm

On Horn-Kapranov uniformisation of the discriminantal loci

Susumu TANABÉ (kumamoto university)

Abstract. In this talk we give a concrete rational uniformisation equation for the discriminantal loci of affine algebraic varieties depending on several deformation parameters. To show this formula we pay attention to the identification of  fibre-integrals (or period integrals) with the hypergeometric function of  Horn and that of Gel'fand-Kapranov-Zelevinski.

Bio. Γεννήθηκε στην Οσάκα, Ιαπωνία το 1964. Αποφοίτησε από το μαθηματικό Τμήμα του Πανεπιστημίου του Τόκιο το 1987. Συνέχισε τις μεταπτυχιακές του σπουδές στο Πανεπιστήμιο της Μόσχας Λομονόσωφ και απέκτησε Master και Διδακτορικό (Μ.Α. 1989, Ph.D. in Mathematical Sciences 1993) με ειδικότητα στην Διαφορικές εξισώσεις. Στην Ακαδημία Επιστημών της Ρωσίας εργάστηκε από το 1993 έως το 1998 ως ερευνητής και ως Lecturer στο Independent University of Moscow (1998-2006). Είναι Καθηγητής στο Μαθηματικό Τμήμα του Πανεπιστημίου Κουμαμότο, στο οποίο διδάσκει από το 2006. Διδάσκει  ανάλυση, γεωμετρία και τοπολογία, ενώ έχει  δημοσιεύσεις σε επιστημονικά περιοδικά σε τομείς όπως: Διαφορικές εξισώσεις, Θεωρία ιδιομορφιών (singularity theory), Δυναμικά συστήματα, αλγεβρική γεωμετρία.

Εκτός από Ιαπωνικά, ξέρει Κινέζικα, Ρώσικα, Πολωνικά, Γερμανικά, Γαλλικά, Ιταλικά, Αγγλικά, Ισπανικά, Ελληνικά. Διαβάζει αρχαία ελληνικά, λατινικά και εβραϊκά.

Δευτέρα 21.12.2009, 3μμ

Monday 21.12.2009, 3pm

On the Complexity of Approximating a Nash Equilibrium

Costis Daskalakis (MIT)

Abstract. According to Bob Aumann, strictly competitive games---a generalization of zero-sum games---are "one of the few areas in game theory, and indeed in the social sciences, where a fairly sharp, unique prediction is made".  We present a generalization of these games to multi-player games played on a network, where the nodes are players and the edges are strictly competitive games between their endpoints; that is, we are looking at a network of competitors. Our generalization of the minmax theorem to the network setting comes with interesting consequences: convexity of equilibria, polynomial-time tractability, and convergence of no-regret algorithms to equilibria.

And what about extending our results beyond zero-sum games? Previous work has established that computing exact equilibria is computationally intractable, but research on approximation algorithms has not made progress beyond finite values of the approximation, while inapproximability results have been evading current techniques. We provide the first inapproximability result for Nash equilibria, for

finite values of relative approximation.

Πέμπτη 19.11.2009, 12μμ

Thursday 19.11.2009, 12pm

Optical biopsy tracking using identification and labeling of probe region within endoscopic images for minimally invasive tissue characterization

Stamatia Giannarou (Imperial College London)

Abstract. The quest for providing tissue characterization and functional mapping during minimally invasive surgery (MIS) has motivated the development of new surgical tools that extend the current functional capabilities of MIS. Miniaturized biophotonic probes can be inserted into the instrument channel of standard endoscopes to reveal cellular and subcellular microstructures of the tissue, allowing excision-free optical biopsy. One of the limitations of such a point based imaging and tissue characterization technique is the difficulty of tracking biopsied sites in vivo.

Since the probe needs to be placed in contact with the tissue when the optical biopsy takes place, tracking the tip of the probe enables the localization of the biopsy site. An image-based approach will be presented for localizing optical probes in endoscopic images without the use of fiducial markers. The colour attributes of the shaft of the probe in the HSV (Hue Saturation Value) space are used to segment the probe in the scene. A novel probabilistic approach has been employed to estimate the orientation of the tangential lines to the shaft of the probe. Perspective image analysis is used to detect the distal tip of the probe.

In order to enable large area surveillance and integrated functional mapping, an image-based tracking framework has been proposed based on SLAM (Simultaneous Localisation and Mapping) for optical probes. This will allow for subsequent localization and contextual analysis of microstructures or guiding real tissue biopsy. The SLAM system is combined with probe tracking to create a 3D model of the tissue surface and spatiotemporally tracked biopsy sites. These biopsy sites are subsequently re-projected back onto the image plane to provide a live augmented view in vivo, thus facilitating retargeting and serial examination.

The proposed method has been validated on ex-vivo and phantom data with known ground truth and the accuracy derived demonstrates the strength and practical clinical value of the technique. The method facilitates a move from the current point based optical biopsy towards large area multi-scale image integration in a routine clinical environment.

Τρίτη 22.09.2009, 2μμ

Tuesday 22.09.2009, 2pm

Secure Computation over Sparse Graphs

Juan Garay (AT&T Labs - Research)

Abstract. We consider networks (graphs) that are not fully connected, and where some of the nodes may be corrupted (and thus misbehave in arbitrarily malicious and coordinated ways) by a computationally unbounded adversary.  It is well known that some fundamental tasks in information-theoretic security, such as secure communication (perfectly secure message transmission), broadcast (a.k.a. Byzantine agreement), and secure multi-party computation, are possible if and only the network has very large connectivity---specifically, Omega(t), where t is an upper bound on the number of corruptions. On the other hand, typically in practical networks most nodes have a small degree, independent of the size of the network; thus, it is unavoidable that some of the nodes will be unable to perform the required task.

The notion of computation in such settings was introduced in Dwork, Peleg, Pippenger and Upfal [STOC'86], where achieving Byzantine agreement with a low number of exceptions on several classes of graphs was considered, and more recently studied by Garay and Ostrovsky [Eurocrypt'08] with regards to secure multi-party computation, which in addition to the correctness requirement of the first type of problem, adds a privacy requirement which might not be satisfied by nodes in bad connectivity situations.

In this talk we review several protocols for the above tasks, as well as security definitions to cope with the security challenges that arise in such partially connected settings.

Τρίτη 15.09.2009, 2μμ

Tuesday 15.09.2009, 2pm

“Privacy-enhancing auctions using rational cryptography”

Nikos Triandopoulos (Boston University)

Abstract:

Due to their widespread use in electronic marketplaces, auctions constitute a central research topic in economics and game theory, and their distributed implementation is an important problem in mechanism design. Securing such implementations, i.e., ensuring that the bidder's privacy is preserved and the final outcome is trustworthy, is crucial in order to retain the economic value of on-line auctions.

In this talk, we present a framework for enhancing with privacy concerns and securely implementing over the Internet a large class of auctions, including sealed-bid single-item auctions and general multi-item multi-winner auctions. We consider a setting where bidders primarily care about monetary payoff, but also they secondarily worry about exposing information about their valuations to other bidders and learning information about other bidders' valuations---that is, bidders are greedy-then-paranoid. To treat privacy explicitly within the game theoretic context, we put forward a new hybrid utility model that considers both monetary and privacy components in bidders' payoffs. We show how to use rational cryptography to approximately implement any given Nash equilibrium of such an auction without a trusted mediator through a protocol that uses only point-to-point authenticated channels between the players. This guarantees that, under cryptographic assumptions, running the protocol is a computational Nash equilibrium with a payoff profile negligibly close to the original equilibrium. We conclude by discussing open problems and interesting research directions in the overlap of game theory and cryptography.

This is joint work with Peter B. Miltersen and Jesper B. Nielsen.

Προηγούμενα έτη