SEMINAR NOTICE

Where do hard instances of Hard problems lie?

Prof. A.K.Pujari, Dean, SCIS

DATE & TIME : 13 September 2013, 4PM VENUE: SEMINAR ROOM, SCIS

Abstract

Hardness analysis of combinatorial has been a vibrant area of research in artificial intelligence. When a domain parameter is made to vary, the hard instances of the problem cluster around a critical value. Thus, there is a phase-transition like situation and the probability of solvability sharply rises from 0 to 1 (or 1 to 0) at the critical value. Understanding this phenomenon becomes important as it provides a very useful insight into the complexity of the problem. Important and popular problems such as SAT, CSP, graph coloring, vertex cover and TSP are known to have phase transition property. The aim of this talk is to introduce and review phase-transition behavior of some hard problems.

BIO

Prof.Pujari is currently Professor of Computer Science and Dean, SCIS, at the University of Hyderabad, Hyderabad. Prior to joining UoH, he served at automated Cartography Cell, Survey of India, and Jawaharlal Nehru University, New Delhi. He received PhD from the Indian Institute of Technology, Kanpur and MSc from Sambalpur University, Sambalpur. He has also undertaken several visiting assignments at the Institute of Industrial Sciences, University of Tokyo; International Institute of Software Technology, United Nations University, Macau; University of Memphis, USA; and Griffith University, Australia, among others. He has published papers in 27 Journals and 35 Refereed Conferences, supervised 17 doctoral students and more than 100 master students, and was investigator for 9 different funded research projects amounting to 1.5 crores.