Beyond NP Revolution
Beyond NP Revolution
Vortrag von Kuldeep Meel
- Veranstaltungsort: APB 2026
- Beginn: 9. April 2019 um 13:30
- Ende: 9. April 2019 um 15:00
- iCal
solving is a central problem in Computer Science. While the mention of SAT can be traced to early 19th century, efforts to develop practically successful SAT solvers go back to 1950s. The past 20 years have witnessed a "NP revolution" with the development of conflict-driven clause-learning (CDCL) SAT solvers. Such solvers combine a classical backtracking search with a rich set of effective heuristics. While 20 years ago SAT solvers were able to solve instances with at most a few hundred variables, modern SAT solvers solve instances with up to millions of variables in a reasonable time. The "NP-revolution" opens up opportunities to design practical algorithms with rigorous guarantees for problems in complexity classes beyond NP by replacing a NP oracle with a SAT Solver. In this talk, we will discuss how we use NP revolution to design practical algorithms for two fundamental problems in artificial intelligence and formal methods: Constrained Counting and Sampling
Bio: Kuldeep Meel is an Assistant Professor of Computer Science in School of
Computing at the National University of Singapore where he holds the Sung
Kah Kay Assistant Professorship. He received his Ph.D. (2017) and M.S.
(2014) degree in Computer Science from Rice University. He holds B. Tech.
(with Honors) degree (2012) in Computer Science and Engineering from Indian
Institute of Technology, Bombay. His research interests lie at the
intersection of Artificial Intelligence and Formal Methods. Meel has
co-presented tutorials at top-tier AI conferences, IJCAI 2018, AAAI 2017,
and UAI 2016. His work received the 2018 Ralph Budd Award for Best PhD
Thesis in Engineering, 2014 Outstanding Masters Thesis Award from Vienna
Center of Logic and Algorithms and Best Student Paper Award at CP 2015. He
