Combinatorial Search Algorithms for Function Evaluation
Staff - Faculty of Informatics
Start date: 19 November 2009
End date: 20 November 2009
The Faculty of Informatics is pleased to announce a seminar given by Ferdinando Cicalese
DATE: Thursday, November 19th, 2009
PLACE: USI Università della Svizzera italiana, room SI-015, Informatics building (Via G. Buffi 13)
TIME: 09.30
ABSTRACT:
In a typical combinatorial search problem one is required to develop a testing procedure to determine which one of a finite number of possible objects or conditions is present. Such problems arise in medical diagnosis, database theory, networking, laboratory analysis, computer decision making, and many other fields.
More precisely, we could define an identification problem as follows:
a) a finite set of objects, O1,... On, from which an initially unknown object has to be identified;
b) a finite set of m tests (or questions) Q1, ..., Qm, to be applied to a single object or to a subset of the n objects in order to gain information about the unknown object which has to be identified;
d) a set of m costs, C1, ..., Cm, where Ci is the cost we incur when we apply test Qi.
In some variants, one also assumes the possibility of erroneous outcomes of some tests and/or additional probabilistic assumptions on the identity of the object to identify.
A solution to the above problem is a deterministic algorithm (decision tree) for choosing which questions to ask such that: (i) the unknown object will always be identified; (ii) as little cost as possible will be incurred.
In this talk, we focus on an instance of the above problem: function evaluation with priced information. This problem has applications in automatic diagnosis, strategic decision making, computer games, database query optimization.
BIO:
Ferdinando Cicalese received his PhD in Computer Science in 2001 at University of Salerno, Italy, where he was appointed ``ricercatore''.
In November 2004, he was awarded the Sofja Kovaleskaja Prize of the Alexander von Humboldt Foundation, Germany. From 2004 until 2009 he led the research group ``Combinatorial Search Algorithms for Bioinformatics'' at the Faculty of Technology of Bielefeld University, Germany. He is associate professor at the Department of Computer Science and Applications, University of Salerno.
His research interests are in different algorithmic aspects of information theory, combinatorial search, and theoretical bioinformatics.
He was co-chair of the International Conference on Combinatorics of Searching Sorting and Coding (COSSAC 2001) and of the Dagstuhl Seminar 09281 on ``Search Methodology'' (2009). He was on the programme committee of the International Latin American Conference on Theoretical Informatics (LATIN'08) and co-editor of a special issue of Discrete Applied Mathematics. He has published more than 50 articles in international journals and proceedings of international conferences. He serves as reviewer for international journals and scientific agencies, such as NSF, AMS, NSA.
Since August 2009, he has been visiting professor in Budapest, at the Alfréd Rényi Institute of Mathematics of the Hungarian Academy of Science.
HOST: Prof. Mauro Pezzè
