Uni-Logo

Direktzugriff

    Abonnieren Sie unseren RSS-Feed

    Die nächsten Termine

    Fakultätskolloquium / Colloquium of the Faculty, Prof. Jiang, National Taiwan University

    Startdatum: 07.08.2018
    Startzeit: 14:00
    Stoppzeit: 16:00

    Beschreibung: 

    Dear colleagues, students & friends of the Faculty of Engineering,

    Dean Prof. Paul and Prof. Scholl would like to cordially invite you to the colloquium of the Faculty of Engineering:

    Prof. Jie-Hong Roland Jiang,
    National Taiwan University
    Title:  "Stochastic Boolean Satisfiability for Games under Uncertainty"

    Date: Tuesday, August 7, 2018
    Time: 14:00 (s.t.)
    Place: Faculty of Engineering, Georges-Köhler-Allee 101, 79110 Freiburg,
    Building 101, Room 02 016/18 (2nd floor)

    Abstract
    Stochastic Boolean Satisfiability (SSAT) is a powerful formalism to represent decision problems under uncertainty, such as belief network inference, probabilistic conformant planning, posteriori hypothesis, and maximum expected utility. In addition to having existential and universal quantifiers as in Quantified Boolean Formulas (QBFs), an SSAT expression may allow randomized quantifiers, and enable compact encoding of decision problems under uncertainty. SSAT is commonly interpreted as Games against Nature. Although SSAT lies in the PSPACE-complete complexity class, same as QBF satisfiability, it receives relatively less attention. In this talk, we focus on two special SSAT formulations under the random-exist quantification and exist-random quantification structures. For the former, we propose an algorithm combining Boolean satisfiability (SAT) and model counting techniques to achieve effective computation. For the latter, we extend the clause selection framework of QBF to SSAT. The method can provide a lower-bound approximate solution when an exact answer is too expensive to compute. Experimental results show some unique benefits of the proposed methods.

    Presenter
    Jie-Hong Roland Jiang is a Professor of the Department of Electrical Engineering and the Graduate Institute of Electronics Engineering at National Taiwan University (NTU). He received his B.S. and M.S. degrees in Electronics Engineering from National Chiao Tung University, Hsinchu, Taiwan, in 1996 and 1998, respectively, and his Ph.D. degree in Electrical Engineering and Computer Sciences from the University of California, Berkeley, in 2004. At NTU, he leads the Applied Logic and Computation Laboratory and have worked on various topics, including logic synthesis, formal verification, electronic design automation, and computation models of biological and physical systems. He is currently a Humboldt Research Fellow visiting Prof. Dr. Christoph Scholl of the University of Freiburg, Germany, in summer 2018, and will be back in 2019.

    Zurück

    Benutzerspezifische Werkzeuge