Stochastic Local Search for Propositional Satisfiability

Speaker: Prof. Abdul Sattar, Griffith University, Australia
Host: Prof. Milind TambeAbstract:
The problem of finding a consistent truth assignment to all propositional variables in a formula, known as SAT problem, has been an interesting and difficult challenge. Indeed, SAT is at the heart of all computationally intractable problems. Many real world problems could be encoded as SAT problems. Thus finding an efficient solution for SAT has far reaching impact on computationally hard problems. This talk will begin with an overview of the main approaches for solving SAT problems. We will then focus on stochastic local search based methods. These methods have been shown to be highly effective for large size problems. We will present our recent results on clause weighting based local search, including an influential method that automatically learns about the structure of the problem, and efficiently exploit those structures to solve some of the difficult challenge problems in the field.Biography:
Prof Sattar is founding Director of the Institute for Integrated and Intelligent Systems (IIIS), a research centre of excellence at Griffith University established in 2003. He is a Research Leader at NICTA Queensland Laboratory since June 2005, and also held the Associate Director of Education portfolio at the Queensland Laboratory from October 2006-June 2008. He has been an academic staff member at Griffith University since February 1992 as a lecturer (1992-95), senior lecturer (1996-99), and professor (2000-present) within the School of Information and Communication Technology. Prior to his career at Griffith University, he was a lecturer in Physics in Rajasthan, India (1980-82), research scholar at Jawaharlal Nehru University, India (1982-85), the University of Waterloo, Canada (1985-87), and the University of Alberta, Canada (1987-1991).He holds a BSc (Physics, Chemistry and Mathematics) and an MSc (Physics) from the University of Rajasthan, India, an MPhil in Computer and Systems Sciences from the Jawaharlal Nehru University, India, and an MMath in Computer Science from the University of Waterloo, Canada, and a PhD in Computer Science (with specialization in Artificial Intelligence) from the University of Alberta, Canada. His current research interests include knowledge representation and reasoning, constraint satisfaction, rational agents, propositional satisfiability, temporal reasoning, temporal databases, and bioinformatics. He has supervised 17 successful completions of PhD graduates, and published over 100 technical papers in refereed conferences and journals in the field. His research team has won three major international awards in recent years (the gold medals for the SAT 2005 and SAT 2007 competitions in the random satisfiable category and an IJCAI 2007 distinguished paper award).

Location: Kaprielian Hall (KAP) - 144

Audiences: Everyone Is Invited

Contact: CS Colloquia