Scaling Discrete Integration via SAT and CSP

Project Description

Decision making with uncertain data is increasingly becoming common in today’s world. Given complex dependencies between modules in a system, and considering the inevitability of noise in observations, the design of symbolic reasoning techniques that can reason about probabilistic nature of systems have emerged as core challenge in the design of AI systems. The objective of this proposal is to develop symbolic reasoning techniques to aid artificial intelligence (AI) systems deal with uncertainty. To this end, this proposal focuses on development of fundamental algorithms for the problem of discrete integration, which is one of central components of symbolic reasoning in modern AI systems.

Research Technical Areas

  • Search and constraint satisfaction
  • Knowledge representation and reasoning
  • Reasoning under uncertainty

Benefits to the society

Discrete integration forms the backbone of probabilistic reasoning, which has wide spread usage in autonomous vehicle, healthcare technologies. CSP and optimization is also at the  core of combinatorial and decision problems which occur quite widely throughout Computer Science and are highly applicable to many sub-problems in the smart-nation context. In a nutshell, this project introduces both academic values to put Singapore in the forefront of AI research and practical values for a safe and secure realization of Singapore smart-nation initiatives.

Project’s Publications

  1. Mate Soos, Kuldeep S. Meel:
    BIRD: Engineering an Efficient CNF-XOR SAT Solver and Its Applications to Approximate Model Counting. AAAI 2019: 1592-1599
  2. Sourav Chakraborty, Kuldeep S. Meel:
    On Testing of Uniform Samplers. AAAI 2019: 7777-7784
  3. Supratik Chakraborty, Kuldeep S. Meel, Moshe Y. Vardi:
    On the Hardness of Probabilistic Inference Relaxations. AAAI 2019: 7785-7792
  4. Rahul Gupta, Shubham Sharma, Subhajit Roy, Kuldeep S. Meel:
    WAPS: Weighted and Projected Sampling. TACAS (1) 2019: 59-76
  5. Yash Pote, Saurabh Joshi, Kuldeep S. Meel:
    Phase Transition Behavior of Cardinality and XOR Constraints. IJCAI 2019: 1162-1168
  6. Shubham Sharma, Subhajit Roy, Mate Soos, Kuldeep S. Meel:
    GANAK: A Scalable Probabilistic Exact Model Counter. IJCAI 2019: 1169-1176
  7. Alexis de Colnet, Kuldeep S. Meel:
    Dual Hashing-Based Algorithms for Discrete Integration. CP 2019: 161-176

Team’s Principal Investigator