DUE TO THE STRIKE THE TALK POSTPONED FOR LATER - STAY TUNED FOR THE NEXT AVAILABLE DATE

Μεταπτυχιακές Σπουδές σε ΗΠΑ και Καναδά

Ph.D. studies in the USA and Canada

Dimitris Paparas 

(Columbia University)

[watch video!]

link will become current shortly before talk

Abstract.  How to apply for Ph.D. studies in the USA. All interested students should attend this seminar. The talk will be in Greek.

Περίληψη: Στόχος της ομιλίας είναι η ενημέρωση για μεταπτυχιακές

σπουδές στην Βόρεια Αμερική και αποτελείται από δυο σκέλη. Στο πρώτο

παρουσιάζουμε τη διαδικασία των αιτήσεων για διδακτορικά και

μεταπτυχιακά και τι πρέπει να προσέξει κανείς. Στο δεύτερο σκέλος, θα

συζητήσουμε σε ποιες περιπτώσεις είναι θετικό να κάνει κάποιος

διδακτορικό στη Βόρεια Αμερική αλλά και πότε θα ήταν καλύτερο να μείνει

στην Ελλάδα, και συγκεκριμένα στο Τμήμα Πληροφορικής και Τηλεπικοινωνιών.

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

Παρασκευή 24.6.2011, 11:00πμ

Friday 24.6.2011, 11:00am

Green Computing

Sartaj Sahni 

(University of Florida)

[watch video!]

link will become current shortly before talk

Abstract.  For decades, computer scientists and engineers have focused on the development of economical computer systems (hardware and software) that are able to solve problems of interest in an acceptable amount of time. Their success in doing this has resulted in an IT industry that accounts for an increasing share of the world’s energy utilization and an increasing share of global carbon dioxide emissions. The current growth rate in energy consumption and carbon dioxide emissions is not sustainable. Sustainability is a new focus for computer systems. Green Computing is concerned with reducing the negative impact that the IT industry is having on the environment. An important impact of the Green Computing revolution on computer scientists and engineers is the addition of energy as a metric in the evaluation of computer systems. Today, we are concerned with the development of economical computer systems that are able to solve problems of interest in an acceptable amount of time and using a minimal amount of energy. This talk will first make the case of Green Computing and then illustrate how algorithmic techniques and trends in the consumer electronics/gaming industries are enabling Green Computing. Illustrative examples include the use of tries to reduce energy consumption in Internet routers and the use of GPUs to reduce the cost of scientific computing.

Τρίτη 31.5.2011, 5:00μμ

Tuesday 31.5.2011, 5:00pm

Rational rotation-minimizing frames on space curves:

theory, algorithms, applications

Rida T. Farouki 

(University of California, Davis,)

[watch video!]

link will become current shortly before talk

Abstract.  An adapted frame along a space curve is an orthonormal vector basis that incorporates the unit curve tangent at each point. Such a frame is said to be rotation-minimizing if its angular velocity maintains a zero component in the direction of the curve tangent, i.e., the normal-plane vectors exhibit no instantaneous rotation about the tangent. Rotation-minimizing frames have useful applications in computer animation, spatial motion design, swept surface constructions, path planning for robotics, and related felds. Recently, the possibility of constructing space curves with exact

rational rotation-minimizing frames (RRMF curves), as a proper subset of the spatial Pythagorean-hodograph (PH) curves, has been recognized. The underlying theory and construction of such RRMF curves is presented, and alternative characterizations for them (in terms of the quaternion and Hopf map representations of spatial PH curves) are derived and compared.

Τετάρτη 26.1.2011, 1:00μμ

Wednesday 26.1.2011, 1:00pm

Moderately exponential approximation

Vangelis Th. Paschos 

(University Paris-Dauphine)

[watch video!]

link will become current shortly before talk

Abstract.  This talk presents a possible trade-off between polynomial approximation and exact computation. We show how using ideas from both fields one can design approximation algorithms for several combinatorial problems achieving ratios that cannot be achieved in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We study in particular maximum independent set and minimum vertex cover.

Τρίτη 11.1.2011, 5:00μμ

Tuesday 11.1.2011, 5:00pm

On the (In)Security of RSA Signatures.

[watch video!]

Aris Tentes 

(New York University)

Abstract. The RSA signature~\cite{RSA76} is one of the most elegant and well known signatures schemes, which is extensively used in a wide variety of applications, and is  the basis of several existing standards such as PKCS \#1. The signature $\sigma$ of the message $m$ is computed as $\sigma= h(m)^d \bmod n$, and verified as $\sigma^e = h(m)\bmod n$, where $(n,e)$ is the RSA public key, $d = e^{-1} \bmod \phi(n)$ is the RSA secret key, and $h$ is an ``appropriate'' hash function. The RSA signature scheme is known to be secure under the standard RSA assumption~\cite{BellareR93,Coron00}, when the function $h$ is modeled as a random oracle. A major open question is whether it is possible to instantiate the hash function $h$ in the standard model, so that the security of RSA signatures can be proven under a ``reasonable'' assumption.

In this work we show that no standard model construction of $h$ allows one to reduce the security of the RSA signatures to any ``reasonable'' assumption, provided  the construction and the reduction treat the multiplicative RSA group $Z_n^*$ in a black-box way. Moreover, we allow $h$ to use multiplications and inversions mod $n$, and also allow the reduction to call the forger on arbitrary values $(n',e')\neq (n,e)$, addressing the main limitations of the prior techniques.

Informally, this means that the construction and the reduction only use the multiplicative structure of $Z_n^*$, and do not gain any additional insight by looking at the specific representation of group elements. To the best of our knowledge,  all known positive results on building ``RSA-type'' signatures (including the standard model constructions of Gennaro-Halevi-Rabin\cite{GennaroHaleviRabin99}, Cramer-Shoup~\cite{CramerShoup00} and Hohenberger-Waters~\cite{HohenbergerW09}) indeed treat $Z_n^*$ as a black-box, and only use its multiplicative structure. Thus, although our results still do not rule out certain types of constructions/reductions,   they seem to cover all successful techniques utilized to date, unlike the prior impossibility results for instantiating RSA signatures due to \citet{Dodis05} and \citet{Paillier07}.

On a positive, we demonstrate the optimality of our negative result by showing that the RSA signatures   can be proven $t$-time secure in the standard model,  under the standard RSA assumption, provided that the description of the hash function $h$ can be proportional to $t$. Finally, and of independent interest, we show how to adopt the influential ``short description'' paradigm of \citet{GennaroT00} from the ``random permutation'' to the ``generic group model".

Joint work with Yevgeniy Dodis and Iftach Haitner

Πέμπτη 23.12.2010, 11:30πμ

Τhursday 23.12.2010, 11:30am

On Evolvability: The Swapping Algorithm, Product Distributions,

and Covariance.

[watch stored video]

Dimitris Diochnos 

(University of Illinois at Chicago)

Abstract. Valiant recently introduced a learning theoretic framework for evolution, and showed that his swapping algorithm evolves monotone conjunctions efficiently over the uniform distribution. We continue the study of the swapping algorithm for monotone conjunctions. A modified presentation is given for the uniform distribution, which leads to a characterization of best approximations, a simplified analysis and improved complexity bounds. It is shown that for product distributions a

similar characterization does not hold, and there may be local optima of the fitness function. However, the characterization holds if the correlation fitness function is replaced by covariance. Evolvability results are given for product distributions using the covariance fitness function, assuming either arbitrary tolerances, or a non-degeneracy condition for the distribution and a size bound on the target.

Τρίτη 21.12.2010, 19:00

Tuesday 21.12.2010, 7:00pm

η ομίλια θα γίνει στο ΑΜΦΙΘΕΑΤΡΟ

Πως να βρίσκετε ψαγμένα τυπάκια σε δευτερόλεπτα.

Dimitris Achlioptas

(University of Athens)

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

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

Η ομιλία δεν προϋποθέτει καμμία γνώση επιστήμης υπολογιστών. Ούτε καν.

Δευτέρα 20.12.2010, 5:00μμ

Monday 20.12.2010, 5:00pm

Efficient Verification of Outsourced Data and Computations.

[watch stored video!]

Charalampos Papamanthou

(Brown U.)

Abstract. With the prevalence of the Internet in every aspect of our life, there has been an increasing interest in remote storage of data and structured information (e.g., emails, photos). This trend has given rise to a new discipline, termed under the name “cloud computing,” widely adopted by many companies (and individuals) in order to save operating and maintenance costs. However, as remote repositories (i.e., the cloud) may lose or modify data due to errors or malicious attacks, it is important to develop methods that provide strong assurance to the users of the integrity of the outsourced data.

In order to address the above problems, one has to take into consideration that the produced solutions are efficient. In other words, if the security added to a cloud service leads to slow performance, the user might reject the service, since, although secure and trusted, the experienced overhead (time, bandwidth) by the service might be unacceptable.

This talk explores integrity checking solutions that go beyond traditional hash-based methods, towards improving efficiency and achieving better asymptotic bounds. The systematic application of

multiple cryptographic primitives, such as accumulators and lattices, leads to the proposal of new authenticated data structures schemes that compare favorably with existing solutions. We conclude by also reporting on some practical work we have done to address the aforementioned problems.

This is joint work with Roberto Tamassia and Nikos Triandopoulos.

The talk is dedicated to the memory of Paris Kanellakis. Paris was a distinguished computer scientist and an esteemed and beloved member of the Brown Department of Computer Science, who died in an airplane crash along with his wife, Maria Teresa Otoya, and their two young children, Alexandra and Stephanos Kanellakis, exactly 15 years ago, on December 20th, 1995. Paris' research area was theoretical computer science, with emphasis on the principles of database systems, logic in computer science, the principles of distributed computing and combinatorial optimization.

Πέμπτη 23.09.2010, 3μμ

Thursday 23.09.2010, 3pm

On the (In)Security of IPsec in MAC-then-Encrypt Configurations.

Jean Paul De Gabrielle

(Royal Holloway U. London)

Abstract. IPsec allows a huge amount of flexibility in the ways in which its component cryptographic mechanisms can be combined to build a secure communications service. This may be good for  supporting different security requirements but is potentially bad for security. We demonstrate the reality of this by describing efficient, plaintext-recovering attacks against all configurations of IPsec in which integrity protection is applied prior to encryption - so-called MAC-then-encrypt configurations. We report on the implementation of our attacks against a specific IPsec  implementation, and reflect on the implications of our attacks for real-world IPsec deployments as well as for theoretical cryptography

2009-2010

   

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