30 October 2019 – A paper co-authored by NUS Computing Sun Kah Kay Assistant Professor Kuldeep Meel was selected for the International Conference on Constraint Programming (CP)’s 25th anniversary volume of selected research papers.
One paper from each year of the conference was chosen for the anniversary volume and Dr Meel’s paper was selected to represent the 2013 conference. CP is an annual research conference for constraint programming, including theory, algorithms, environments, languages, models, systems, and applications.
Dr Meel co-authored the paper, “A Scalable Approximate Model Counter”, Prof Supratik Chakraborty (IITB) and Prof Moshe Vardi (Rice) while pursuing his Masters degree at Rice University. Their paper presented the first scalable approximate model counter.
“Model counting is one of the fundamental problems in computer science and it is defined as the problem of counting the number of solutions produced by a system of constraints,” said Dr Meel. “For such systems, exact counting can be computationally difficult and therefore, significant efforts have been invested into designing and analysing approximate algorithms to solve this problem.”
While conducting the study in 2012, Dr Meel and his collaborators found a massive gap between theory and practice – existing techniques that provided strong approximation guarantees did not scale well in practice and techniques that scaled well had weak or no provable approximation guarantees. The team proceeded to develop their own approximate counter, named ApproxMC, that came with provable approximation guarantees. Over the past six years, Dr Meel and his team have enhanced the capabilities of ApproxMC to handle problems with millions of variables. The latest version of ApproxMC was published in the 2019 AAAI Conference on Artificial Intelligence.
“It has been a long journey since the time we started,” said Dr Meel. “ApproxMC’s ability to scale for industry-sized problems and provide rigorous approximation guarantees has led to other researchers from diverse domains use our tools as the backend engine in their work. While the bridge between theory and practice has been partly bridged, there is still a lot more work that needs to be done. Fortunately, this is an active area of research and we hope to break the million variables barrier and go further.”
“CP is the leading conference in my research area and is close to my heart as some of my favourite papers were published at CP. It is truly an honour to have our paper recognised,” Dr Meel added.
