Seminars

you must be logged-in to have full access to seminar attachments

Graph Searching Games

Date: 
25 September, 2009 - 12:00 - 12:30
Location: 
Aula Multimediale DIMI
Description
Abstract: 

Tree-width is a well-known metric on undirected graphs that measures how tree-like a graph is. Tree-width is characterized by a game known as the cops-and-robber game, where a number of cops chase a robber on the graph. Aside from their interest in graph structure theory, these notions have also proved very useful in the development of algorithms. Many problems that are intractable in general can be solved efficiently on graphs of bounded tree-width (e.g., finding a Hamiltonian cycle in a graph or detecting if a graph is three-colorable).

Game Theory: beyond Nash equilibrium

Date: 
25 September, 2009 - 11:30 - 12:00
Location: 
Aula Multimediale DIMI
Description
Abstract: 

Games theory is that branch of mathematics studying situations where the agents (players) must face some choices. Depending on all players' choices each player has an utility. The set of choices taken by a player constitutes his strategy.
Games theory tries to find good strategies (that is, pursuing some notion of equilibrium) and to explain some social behaviours of the real life. The most commonly-used notion of equilibrium is the Nash equilibrium. It gives an intuition about what people do, it explains some behaviour, but it does not tollerate "faulty" or "unexpected" behaviour, it does not deal with coalitions, it does not take computational aspects into account, and it does not deal with cases where the players are not aware of all aspects of the game. Here, I perform an epistemological analysis about game theory and Nash equilibrium.

On simple infinitely satisfiable formulae when foundation is withdrawn

Date: 
29 June, 2009 - 15:00 - 15:45
Location: 
Sala Riunioni DIMI
Description
Abstract: 

It is known that the Axiom of Infinity can be expressed by stating the existence of sets satisfying a formula of low structural complexity, which involves only universal restricted quantifiers (i.e., belonging to the Bernays-Schonfinkel-Ramsey class). We will present two similar formulae of the BSR class, both incompatible with the axiom of foundation, but satisfiable in a context such as the Aczel's theory of hypersets. Even if the BSR class has recently been proved to be semi-decidable, by showing that every infinite model of such a formula can be finitely representable by means of a hereditarily finite family of hypersets, the formulae at hand do not exhibit such a property. This may be a clue that the collection of satisfiable BSR formulae requires for hyperset theory -- if decidable at all in that context -- a significantly more challenging decision algorithm than for the standard Zermelo-Fraenkel set theory.

Solutions to NP-complete problems

Location: 
DIMI, University of Trieste
Description
Abstract: 

Four lectures held by Prof. John Abela from University of Malta, as part of a course 'Algoritmi Avanzati' taking place in Trieste.

The schedule of the lectures is
5th April, Tuesday, 11.00 - 13.00 & 14.00 - 16.00
7th April, Thursday, 11.00 - 13.00 & 14.00 - 16.00

Syndicate content