Home > Academic Announcements > (May 17) The Arts of Satisfiability: Algorithms and Complexity

(May 17) The Arts of Satisfiability: Algorithms and Complexity

Last updated :2019-05-14

Topic: The Arts of Satisfiability: Algorithms and Complexity
Speaker: Professor CHEN Jianer
(Guangzhou University)
Host: Professor LI Lvzhou
Time: 10:30-11:30, Friday, May 17, 2019
Venue: A101, School of Data and Computer Science, Guangzhou East Campus, SYSU

Abstract:
The Satisfiability problem (SAT) and its optimization version Max-SAT have been central to the research in computer science with wide applications in many areas such as software testing, AI, bioinformatics, and computational optimization. In this talk, we will focus on the theoretical advances and recent progresses in the study of algorithms and complexity of SAT and MaxSAT problems. We study the complexity of the problems and survey techniques that have been proven effective in development of algorithms for the problems. In particular, we will present in detail some new techniques based on resolution and domination that lead to faster algorithms for the problems.