Giorgio Ausiello: The Making of a New Science

At “Sala riunioni”, first floor, Dipartimento di Ingegneria, Via della Vasca Navale 79, 00149 Roma, Italy
On Friday, November 16, 2018
From 2pm to 3pm

The seminar will feature a presentation by prof. Giorgio Ausiello and a presentation of his recent book “The Making of a New Science”.

Please refer to the information below for more details.

Thanks,
Donatella

Abstract: The cost of hyperpaths in directed hypergraphs can be measured in various different ways, which have been used in a wide set of applications. Depending on the considered measure function the cost to find optimum hyperpaths may range from NP-hard to linear time. A first solution for finding optimum hyperpaths in case of a superior functions can be found in a seminal work by Knuth, which generalizes Dijkstra’s Algorithm to deal with a grammar problem. In this presentation we first provide a gentle introduction to directed hypergraphs, their properties and their applications; then we define a hierarchy of classes of optimization problems regarding the computation of shortest hypapaths which are based on the properties of the cost measures.

Bio: Giorgio Ausiello is Professor Emeritus of Sapienza University of Rome and is among the pioneers of theoretical computer science. Throughout his research career Ausiello has addressed various research domains ranging from theory of programming to algorithms and complexity. Ausiello has contributed to several initiatives for the development of theoretical computer science in Italy and in Europe. In 1972 he was among the founders of the European Association for Theoretical Computer Science (EATCS) of which he has been President from 2006 to 2009. In 2014 he has been nominated Fellow of EATCS. From 2001 to 2015 Ausiello has been Editor in Chief of the Theoretical Computer Science (journal) Series A (Algorithms, Automata, Complexity and Games).