Quand: Le lundi 9 décembre 2019 à 14h00
Où: En A007, à Télécom SudParis, Evry
Titre: Solving Stochastic Boolean Satisfiability of Formulas with Two Quantification Levels

Speaker:
Jie-Hong Roland Jiang, National Taiwan University

Abstract:
Stochastic Boolean Satisfiability (SSAT) is a powerful formalism to represent computational problems with uncertainty, such as belief network inference, probabilistic planning, posteriori hypothesis, maximum expected utility, etc. Solving SSAT formulas lies in the PSPACE-complete complexity class same as solving Quantified Boolean Formulas (QBFs). While many endeavors have been made to enhance QBF solving in recent years, SSAT has drawn relatively less attention. In this seminar, we examine the special classes of SSAT formulas with two quantification levels. By combining SAT, QBF, and model counting techniques, we develop SSAT solvers with distinct advantages.

(This seminar is based on the joint work with Nian-Ze Lee and Yen-Shi Wang published in IJCAI 2017 and 2018.)

Biography:

Jie-Hong (Roland) Jiang is a Professor of the Department of Electrical Engineering, Graduate Institute of Electronics Engineering, and Genome and Systems Biology Degree Program at National Taiwan University (NTU). He leads the Applied Logic and Computation Lab, and has worked extensively on logic synthesis, formal verification, electronic design automation, and computation models of biological and physical systems. He has conducted several government and industry sponsored research projects, including three international joint projects. His work was recognized as a distinct paper in the 2011 International Conference on Computer Aided Verification (CAV), and was nominated for best papers in the 2007 IEEE/ACM International Conference on Computer-Aided Design (ICCAD) and in the 2010 and 2016 ACM/IEEE Design Automation Conference (DAC). He received the Academic Excellence Awards of the EECS College at NTU in 2011 and 2013, Distinguished Young Scholar Award of the Taiwan IC Design Society in 2012, NTU Outstanding Teaching Award in 2013, 2014, and 2016, Humboldt Research Fellowship for Experienced Researchers in 2018-2019, Best Advisor Award of the 2013 Synopsys APPs Design Contest, and other thesis advisory awards.