Kuldeep S. Meel

Sung Kah Kay Assistant Professor
Computer Science Department, School of Computing
National University of Singapore
Office: COM2-03-41
Phone (O): +65-651 61422
Email: meel@comp.nus.edu.sg
Please consult my calendar before suggesting a meeting time.
Research Group Website

Short Bio

Kuldeep Meel is an Sung Kah Kay Assistant Professor in the Computer Science Department of School of Computing at National University of Singapore. The broader goal of his research is to advance artificial intelligence techniques, which utilize ubiquity of data and formal methods, to enable computing to deal with increasingly uncertain real-world environments.

I am looking for highly motivated Ph.D. students, postdocs, and interns (with time commitment of at least 6 months) in our group. Read this before sending me an email.


Research Interests

  • Constrained Sampling and Counting         
  • Artificial Intelligence
  • Knowledge Representation and Reasoning
  • Formal Methods
  • Interpretable Models


Students & Postdocs

I am proud of my highly motivated students and postdocs:
  • Bishwamittra Ghosh, PhD Student (Since: Spring 2018)
  • Lorenzo Ciampiconi, MS@Politecnico di Milano (expected: May 2019)
  • Alexis de Colnet, MComp@NUS (expected: May 2019)
  • Rahul Gupta, BTech+MTech@IITK (expected: May 2019) , co-advised with Subhajit Roy (IITK)
  • Shubham Sharma, BTech+MTech@IITK (expected: May 2019), co-advised with Subhajit Roy (IITK)
  • Do Andre Khoi Nguyen, Undergraduate Researcher (Since: May 2018)


  • Dr. Mate Soos, Research Fellow (March 2018 -- June 2018)
  • Bhavishya, Summer Intern (May 2018 - July 2018)




Awards and Honors


Selected Publications

Google Scholar
The names of authors are sorted alphabetically and the order does not reflect contribution.
Counting-Based Reliability Estimation for Power-Transmission Grids
Leonardo Duenas-Osorio, Kuldeep S. Meel, Roger Paredes, and Moshe Y. Vardi
Proceedings of AAAI Conference on Artificial Intelligence (AAAI), 2017.
Modern society is increasingly reliant on the functionality of infrastructure facilities and utility services. Consequently, there has been surge of interest in the problem of quantification of system reliability, which is known to be #P-complete. Reliability also contributes to the resilience of systems, so as to effectively make them bounce back after contingencies. Despite diverse progress, most techniques to estimate system reliability and resilience remain computationally expensive. In this paper, we investigate how recent advances in hashing-based approaches to counting can be exploited to improve computational techniques for system reliability. The primary contribution of this paper is a novel framework, RelNet, that provides provably approximately correct (PAC) estimates for arbitrary networks. We then apply RelNet to ten real world power transmission grids across different cities in the U.S. and are able to obtain, to the best of our knowledge, the first theoretically sound a priori estimates of reliability between several pairs of nodes of interest. Such estimates will help managing uncertainty and support rational decision making for community resilience.
Algorithmic Improvements in Approximate Counting for Probabilistic Inference: From Linear to Logarithmic SAT Calls
Supratik Chakraborty, Kuldeep S. Meel, and Moshe Y. Vardi
Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), 2016.
Probabilistic inference via model counting has emerged as a scalable technique with strong formal guarantees, thanks to recent advances in hashing-based approximate counting. State-of-the-art hashing-based counting algorithms use an {\NP} oracle, such that the number of oracle invocations grows linearly in the number of variables n in the input constraint. We present a new approach to hashing-based approximate model counting in which the number of oracle invocations grows logarithmically in $n$, while still providing strong theoretical guarantees. Our experiments show that the new approach outperforms state-of-the-art techniques for approximate counting by 1-2 orders of magnitude in running time.
On Computing Minimal Independent Support and Its Applications to Sampling and Counting
Alexander Ivrii, Sharad Malik, Kuldeep S. Meel, and Moshe Y. Vardi
Proceedings of International Conference on Constraint Programming (CP), 2015.
Best Student Paper Award
Constrained sampling and counting are two fundamental problems arising in domains ranging from artificial intelligence and security, to hardware and software testing. Recent approaches to approximate solutions for these problems rely on employing SAT solvers and universal hash functions that are typically encoded as XOR constraints of length n/2 for an input formula with n variables. As the runtime performance of SAT solvers heavily depends on the length of XOR constraints, recent research effort has been focused on reduction of length of XOR constraints. Consequently, a notion of Independent Support was proposed, and it was shown that constructing XORs over independent support (if known) can lead to a significant reduction in the length of XOR constraints without losing the theoretical guarantees of sampling and counting algorithms. In this paper, we present the first algorithmic procedure (and a corresponding tool, called MIS) to determine minimal independent support for a given CNF formula by employing a reduction to group minimal unsatisfiable subsets (GMUS). By utilizing minimal independent supports computed by MIS, we provide new tighter bounds on the length of XOR constraints for constrained counting and sampling. Furthermore, the universal hash functions constructed from independent supports computed by MIS provide two to three orders of magnitude performance improvement in state-of-the-art constrained sampling and counting tools, while still retaining theoretical guarantees.
Distribution-Aware Sampling and Weighted Model Counting for SAT
Supratik Chakraborty, Daniel J. Fremont, Kuldeep S. Meel, Sanjit A. Seshia, and Moshe Y. Vardi
Proceedings of AAAI Conference on Artificial Intelligence (AAAI), 2014.
Given a CNF formula and a weight for each assignment of values to variables, two natural problems are weighted model counting and distribution-aware sampling of satisfying assignments. Both problems have a wide variety of important applications. Due to the inherent complexity of the exact versions of the problems, interest has focused on solving them approximately. Prior work in this area scaled only to small problems in practice, or failed to provide strong theoretical guarantees, or employed a computationally-expensive maximum a posteriori probability (MAP) oracle that assumes prior knowledge of a factored representation of the weight distribution. We present a novel approach that works with a black-box oracle for weights of assignments and requires only an {\NP}-oracle (in practice, a SAT-solver) to solve both the counting and sampling problems. Our approach works under mild assumptions on the distribution of weights of satisfying assignments, provides strong theoretical guarantees, and scales to problems involving several thousand variables. We also show that the assumptions can be significantly relaxed while improving computational efficiency if a factored representation of the weights is known.

Full list of publications is available here



  • Organizer: 1st Workshop on Probabilistic Reasoning and Formal Methods. Co-organized with S. Akshay (IIT Bombay)
  • Program Committee: AAAI 2019, CoDS-COMAD 2019, IJCAI 2018, AAAI 2018, CP 2018, FAW 2018, CP 2017, CAV-16 Artifact Evaluation
  • Reviewer: CACM (2014, 2018), JAIR (2018), Algorithms (2018), ACM TOPLAS (2017), IJCAR (2018), NFM (2018), SAT 2017, TACAS 2017, SAT 2016, CAV 2015, FoSSaCS 2015, DAC 2014
  • Part of 12 member AAAI 2015 Futures Focus Group tasked with creation of vision for AAAI



  • 08 August 2018

    I am deeply honored to be appointed Sung Kah Kay Assistant Professor at School of Computing. The chair is established in the memory of Dr. Sung Kah Kay, who (with his wife, Jennifer Loo) passed away in Singapore Airlines crash in Taipei in 2000. Quoting Dr. Sung Kah Kay’s parents, who along with friends established the chair: “To us, it was a meaningful way of making our memory of Kah Kay come alive. His untimely departure was a great loss to us. But besides our loss, Kah Kay’s own loss was his unfulfilled dream of computer research work which was his life and passion”. I am thankful and honored to have been entrusted to contribute to Kah-Kay’s dream.

  • 20 June 2018

    I will be at IJCAI from July 12 – July 19 and at Leiden University on July 20. I will be co-presenting tutorial with Supratik Chakraborty at IJCAI on July 13.

  • 16 June 2018

    I am visiting MPI-SWS and INRIA Rennes for the next two weeks (i.e. June 16 – June 30).

  • 04 June 2018

    Submitted our paper Network Reliability Estimation in Theory and Practice to the journal: Reliability Engineering & System Safety

All news…

Old Profile: Kuldeep Meel: High-Risk, High-Reward Research



I am looking for highly motivated Ph.D. students, postdocs, and interns (with time commitment of at least 6 months) in our group.

  • If you are a student at NUS, feel free to drop by my office or schedule a meeting with me. (See my calendar).
  • Otherwise, please send me an email with your CV if you are interested. If you are looking for an internship/postdoc, make sure your subject contains the word "olleh" and you should include reviews of two of my papers (published in the previous 3 years). The reviews should be in the body of the email (and not as pdf). Furthermore, the body of your email should contain the phrase: "Here are two papers that I have reviewed". A strong background in statistics, algorithms/formal methods and prior experience in coding is crucial to make a significant contribution to our research.