Corso di “Complexity theory: from decision to functional problems” – Prof. Filippo Furfaro (22 Maggio – 5 Giugno 2017)

Course Title:

“Complexity theory: from decision to functional problems”
Abstract:

“The course aims at giving an insight on the complexity classes for decisional problems inside P and beyond NP.
Starting from the formal definitions of these classes, the students will excercise and improve their ability
in proving membership and hardness results for several problems against these classes.
Alternative paradigms for characterizing the complexity will be discussed (descriptive complexity, parametrized complexity).
Finally, the complexity characterization of counting and function problems will be investigated, focusing on the classes
FP, #P, and FP^O (i.e., FP with queries to an oracle in class O).”

 

Course schedule:

Monday 22 May – h 15.30-18.30 – Aula seminari Cubo 44

Thursday 25 May – h 15.00-18:00 – Aula seminari Cubo 44

Monday 29 May – h 15.30-18:30 – Aula seminari Cubo 44

Monday 5 June, h 15.30 – 18:30 – Aula seminari Cubo 44
Brief CV:

Filippo Furfaro received the PhD degree in “Computer science and systems engineering” from the University of Calabria. He is an associate professor at the University of Calabria. His research interests include databases, web and semistructured data management, multidimensional data compression, inconsistent data management, RFID data management, and process mining.