[Παλιό] -- Σεμινάριο Αλγορίθμων

Post by **Ethel** » Wed Nov 16, 2005 10:29 am

Tο Σεμινάριο Αλγορίθμων του Τμήματος Πληροφορικής και Τηλεπικοινωνιών ξεκινά τη νέα χρονιά με την εξής ομιλία:
Eυριπίδης Μάρκου (ΕΚΠΑ)
Αναζήτηση μαύρης τρύπας σε (ημι-)συγχρονισμένα δίκτυα
Πα 25 Noεμβρίου, 12.00.
Aίθουσα Τηλεσυσκέψεων, 2os όροφος, Kέντρο Δικτύων
Η περίληψη ακολουθεί, ενώ γενικές πληροφορίες βρίσκονται στην σελίδα: http://www.di.uoa.gr/~emiris/seminar/.
Η ομιλία θα μεταδοθεί σε πραγματικό χρόνο στο διαδίκτυο. Για URL και οδηγίες βλ.: http://lessons.di.uoa.gr/mediacenter.php

Searching for a black hole in (semi-)synchronous networks

We study how to explore efficiently an insecure network, namely a network that may contain a hostile node called black hole introduced by S. Dobrev, P. Flocchini, G. Prencipe, and N. Santoro (2001).

A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of locating a black hole in a (partially) synchronous network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable to identify a black hole is two. For a given graph and given starting node we are
interested in the fastest possible black hole search by two agents.

For arbitrary trees, a 5/3 approximation algorithm has been given by J. Czyzowicz, D. Kowalski, E. Markou, and A. Pelc, while optimal algorithms have been given for special classes of trees (2004). R. Klasing, E. Markou, T. Radzik, and F. Sarracco proved that the problem is NP-hard (even in planar graphs) and gave a 27/8 approximation algorithm for arbitrary graphs (2005).

A variation of the problem where there is a subset of nodes known to be safe, had been also proved NP-hard by J. Czyzowicz, D. Kowalski, E. Markou, and A. Pelc, while they gave a 9.3 approximation algorithm (2004). Finally R. Klasing, E. Markou, T. Radzik, and F. Sarracco improved this approximation ratio to 6 and they showed that both versions of the problem are APX-hard (2005).

Paralias · Post by **Paralias** » Wed Nov 16, 2005 11:51 pm

Σκέφτεται κανείς να πάει;

AnINffected · Post by **AnINffected** » Thu Nov 17, 2005 12:39 pm

Φαίνεται ενδιαφέρον και για τους σεκιουριτάδες (ξέρετε τι εννοώ)

Αν ήταν στο Πανεπιστήμιο μας θα ερχόμουν.

Post by **The Punisher** » Fri Dec 02, 2005 5:45 pm

Και το σεμινάριο συνεχίζεται....

Περισσότερα εδώ...
Υ.Γ Αυτό πως σας φαίνεται?

AnINffected · Post by **AnINffected** » Fri Dec 02, 2005 7:04 pm

Πολύ καλό!Μπράβο!
Θα βάλω Real

Post by **The Punisher** » Fri Dec 02, 2005 10:28 pm

Συγγνώμη,δε σε έπιασα...Real???

AnINffected · Post by **AnINffected** » Sat Dec 03, 2005 3:59 am

Real Player
Το πρόγραμμα που χρειάζεσαι για να παρακολουθήσεις το βίντεο της διάλεξης.
http://www.real.com

Post by **The Punisher** » Sat Dec 03, 2005 11:05 am

A, ok. Απλά δεν κοίταξα όλη τη σελίδα...και έχασα μάλλον την πιο σημαντική λεπτομέρεια!!

AnINffected · Post by **AnINffected** » Wed Dec 07, 2005 2:04 pm

Αρχίζει σε κανα 10λεπτο για όποιον ενδιαφέρεται!

Post by **Ethel** » Sat Dec 17, 2005 4:46 pm

Σεραφείμ Μπατζόγλου (Stanford U.)

The role of Computation in Genetics today

Τε 20 Δεκεμβρίου, 3.00μμ (ακριβώς)
Aίθουσα Τηλεσυσκέψεων, 2os όροφος, Kέντρο Δικτύων

γενικές πληροφορίες βρίσκονται
στην σελίδα: http://www.di.uoa.gr/~emiris/seminar/.
Η ομιλία θα μεταδοθεί σε πραγματικό χρόνο στο διαδίκτυο,
βλ.: http://lessons.di.uoa.gr/mediacenter.php

Περίληψη

The role of Computation in Genetics today

Biologists in the 20th described the basic molecular processes governing
life: (1) the "genetic dogma", describing how information in DNA is
expressed into function within each cell; and (2) "evolution", describing
how random changes in genetic information lead to adaptation of a variety
of species. Today, biology is changing rapidly from a descriptive science,
to a quantitative, information science. This change is driven by new
technologies that enable high-throughput generation of biomolecular data.
For example, we can now decipher the exact sequence of letters in our DNA;
also, we can measure the activity of all genes in a cell with a single,
inexpensive measurement.

As a result, computation has taken a central role in molecular biology.
Both the collection and the analysis of high-throughput biological data
require the use of sophisticated algorithms and software. In this talk,
I will follow the genetic dogma, "DNA -> gene transcript -> protein ->
cell" and show examples of the role of computation in quantifying each of
these steps: sequencing of DNA, prediction of gene transcripts, comparison
of proteins, and analysis of protein interactions that govern the functions
of a cell. I will also show examples of comparative genomics, where we
study how evolution works at the molecular level by comparing biological
data from many organisms, and more importantly how we can use these
comparisons to increase signal-to-noise ratio in our data and to better
understand the biology of a given organism.

AnINffected · Post by **AnINffected** » Tue Dec 20, 2005 12:07 am

Ευχαριστούμε Τζένη...

Την προηγούμενη το Real μου πέταξε General Error 10' πρίν ξεκινήσει και δε πρόλαβα να λύσω το πρόβλημα.Χρειάζεται να είμαστε εγγεγραμμένοι κάπου για να μπορέσουμε να τα παρακολουθήσουμε;

Post by **Ethel** » Tue Dec 20, 2005 10:05 am

Δεν ξέρω αλλά δεν νομίζω

Post by **Ethel** » Wed Jan 11, 2006 8:09 pm

Συνέχεια

Κώστας Δασκαλάκης (UC Berkeley)

The Complexity of Nash Equilibria

Πα 13 Ιανουαρίου, 1.00μμ
*** Aίθουσα Δ' ***

---
Περίληψη

The Complexity of Nash Equilibria

In 1951, Nash showed that every game has a mixed Nash equilibrium.
His proof is a reduction to Brouwer's fixpoint theorem and places
the problem of finding equilibria into the realm of 'exponential
existence proofs'. In fact, whether Nash equilibria can be computed
in polynomial time has remained open since that time, and has come
under increased scrutiny during the past two decades. In this talk,
I will present some recent results (joint work with Paul Goldberg
and Christos Papadimitriou) that shed light to this problem, in
the negative direction.

Post by **Ethel** » Wed Feb 15, 2006 5:19 pm

Και συνεχίζουμε...

Tο Σεμινάριο Αλγορίθμων του Τμήματος Πληροφορικής
και Τηλεπικοινωνιών συνεχίζεται με την εξής ομιλία:

Alexandros Kalousis (U Geneva)

A Unifying Framework for Relational Distance Based
Learning Over the Relational Algebra Formalism

Πα 17 Φεβρουαρίου, 11.00
Aίθουσα Συνεδρ. Iσoγείου

Περίληψη

A Unifying Framework for Relational Distance Based Learning
Over the Relational Algebra Formalism

We will present a general framework based on concepts of relational
algebra for distance based learning over relational schemata. The
advantage of the proposed framework is that it requires no
transformation of the representation of data that come in the form
of relational databases. It is directly applicable to any relational
database without the need of type and mode definitions and conversions
to logic programming as it is the case with most relational learning
systems based on Inductive Logic Programming.

Our framework builds on the notions of tuples of relations and sets
of tuples. We show how exploiting these elementary building blocks our
learning examples are represented via tree like structures. In order to
define distances between relational examples we will explore two avenues.
Both of them are based on the definition of simple operators on tuples
and sets of tuples which are subsequently combined in order to provide a
global operator on the full relational structure. The first approach is
based on the use of classical distances over tuples and sets of tuples
and the second one on the definition of kernels.

The user of the system has at his disposal a number of possible distance
operators from which he can choose, or alternatively, to what amounts to
"model selection", can let the system perform the selection automatically.
Some results on well known relational datasets will be presented.

Post by **Ethel** » Fri Feb 17, 2006 1:10 pm

Δεν πτοούμαι θα πω κι άλλα...

Βαγγέλης Μαρκάκης (U Toronto)
Computational Aspects of Game Theory and Microeconomics
Tε 22 Φεβρουαρίου, 1.00 μμ
Αίθουσα Τηλεσυσκέψεων, 2os όροφος, Kέντρο Δικτύων

Περίληψη

Computational Aspects of Game Theory and Microeconomics

Game theory and economics provide a mathematical framework for
analyzing interactions among self-interested agents. However,
the outcomes proposed by the economic theory often involve
optimization problems with no known efficient algorithms.

In this talk we will study the computational complexity of
various economic solution concepts. The first part of the talk
will focus on the problem of allocating a set of indivisible
goods to a set of agents, who express preferences over combinations
of items through their utility functions. Several objective
functions have been considered in the economic literature in
different contexts. In fair division theory, a desirable outcome
is to produce an allocation that minimizes the envy between the
agents or achieves additional fairness criteria. In the context
of auctions, an alternative goal is to maximize the social
welfare, i.e., the total utility derived by the agents. We provide
new approximation algorithms as well as hardness results for
these objectives, for various types of utility functions. The
second part will focus on computing or approximating equilibrium
concepts in games. I will present a result on approximating Nash
equilibria (outcomes from which no player has an incentive to
deviate) in noncooperative games.

Parts of this talk represent joint work with Richard Lipton, Amin
Saberi, Aranyak Mehta, Subhash Khot and Elchanan Mossel.

Post by **Ethel** » Thu Apr 06, 2006 5:33 pm

David Pearce (Rey Juan Carlos University)

A Logic for Reasoning about Well-Founded Semantics

Τε 12 Απριλίου, 3.00 μμ
Αίθουσα Τηλεσυσκέψεων, 2os όροφος, Kέντρο Δικτύων

Περίληψη

A Logic for Reasoning about Well-Founded Semantics
(joint work with Pedro Cabalar & Sergei Odintsov)

Of the various proposals for dealing with default negation in logic programming that go beyond the methods of ordinary Prolog, the Well-Founded Semantics (WFS) of Van Gelder, Ross and Schlipf (1991) has proved to be one of the most attractive and resilient. Particularly its favourable computational properties have made it popular among system developers and the well-known implementation XSB-Prolog is now extensively used in AI problem solving and applications in knowledge representation and reasoning. This talk discusses the logical foundations of WFS and proposes a solution to a long-standing open problem: how to characterise partial stable and well-founded models as minimal models in a suitable nonclassical, non-modal logic. We thereby obtain a deductive base logic for well-founded inference as well as a means to extend WFS to disjunctive programs and arbitrary propositional theories. A major challenge is to axiomatise the base logic.

Post by **The Punisher** » Tue Jul 11, 2006 2:47 pm

Πα 14 Ιουλίου,12.00 ***Aίθουσα Δ' ***
Άγγελος Κιαγιάς (U. Connecticut)
Mathematics of Internet Security

This talk will present some of the mathematics behind the asymmetric cryptographic techniques that are used to provide secure communications over the Internet. Number theory, probability, combinatorics and computational complexity are all beautifully glued together to solve the paradox of creating a secure channel using only insecure network communication. Key-exchange, discovered over 30 years ago, remains today still one of the major research subjects in cryptography and many aspects of it are far from being understood. The talk will assume only basic background on analysis of algorithms, probability and discrete mathematics.

...Θα προσπαθήσω να το τιμήσω !

Post by **HdkiLLeR** » Tue Jul 11, 2006 3:03 pm

Εάν είναι θα περάσω και εγώ

AnINffected · Post by **AnINffected** » Tue Jul 11, 2006 10:51 pm

David Pearce (Rey Juan Carlos University)

A Logic for Reasoning about Well-Founded Semantics

Τε 12 Απριλίου, 3.00 μμ
Αίθουσα Τηλεσυσκέψεων, 2os όροφος, Kέντρο Δικτύων

Τώρα το είδα αυτό...
Γίνεται και από απόσταση;

Για το δεύτερο, δύσκολο να έρθω στη σχολή αυτές τις μέρες, αλλά who knows...?
Πάντως πρέπει να είναι must για όσους θέλουν να ασχοληθούν με την Ασφάλεια!

Post by **Ethel** » Wed Jul 12, 2006 12:53 pm

Παίδες δεν ξέρω αν το χετε καταλάβει αλλά μιλάμε για Πληροφορική ΕΚΠΑ, όχι ΟΠΑ.
Άρα πρέπει να ανηφορίσετε για τα σεμινάρια αυτά...

Post by **The Punisher** » Wed Jul 12, 2006 1:02 pm

Φυσικά και το ξέρω..τουλάχιστον εγώ. Είχα πάει σε ένα άλλο σεμινάριο, όχι του Εμιρη. Πάντως για όσα γίνονται στην αίθουσα Τηλεδιάσκεψης δε σημαίνει και απαραίτητα ότι χρησιμοποιούν και το εξοπλισμό για Τηλεδιάσκεψη, απλά χρησιμοποιούν την αίθουσα!

Post by **Ethel** » Wed Jul 12, 2006 1:13 pm

Ναι I know ότι εσύ το ξέρεις

, στον hd και στον Aninffected πήγαινε η επισύμανση...

HdkiLLeR wrote:Εάν είμαι στο κεντρικό θα περάσω και εγώ

AnINffected wrote:δύσκολο να έρθω στη σχολή αυτές τις μέρες, αλλά who knows...?