Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Toronto

$36,000.00

Scalable Next Generation Automated Reasoning Techniques

FY 2024-25

Summary
This project focuses on the development of scalable automated symbolic reasoning techniques and their integration with statistical reasoning methods to enable the development of provably robust, reliable, and trustworthy computing systems. The current generation of symbolic reasoning techniques excel at qualitative tasks; such techniques sufficed for traditional systems whose design sought to achieve deterministic behavior. In contrast, modern computing systems crucially rely on statistical methods to account for the uncertainty in the environment and to reason about the behavior of these systems. The proposed research program will focus on developing the next generation of automated reasoning techniques that can perform higher-order tasks such as quantitative measurement, sampling of representative behavior, and automated synthesis of systems. From a core technical perspective, the project builds on the SAT revolution, which refers to algorithmic advances in combinatorial solving techniques for the fundamental problem of satisfiability (SAT), i.e., whether it is possible to satisfy a given set of constraints. The SAT revolution offers the opportunity to develop scalable techniques for problems that lie beyond SAT from a complexity perspective and, therefore, stand to benefit from the availability of powerful SAT engines. Our project seeks to enable a Beyond SAT revolution via the design of scalable techniques for two fundamental problems that lie beyond SAT: Constrained counting and constrained sampling, In constrained counting, the task is to count the total weight, subject to a given weight function, of the set of solutions of input constraints. In constrained sampling, the task is to sample randomly, subject to a given weight function, from the set of solutions. Even the approximate variants of these problems are known to be computationally intractable, and therefore, despite strong theoretical and practical interest over the years, there is still an immense gap between theory and practice. Our recent work in counting and sampling has yielded dramatic progress. By combining the ideas of using SAT solving as an oracle and the reduction of the solution space via universal hashing, we have developed highly scalable algorithms that offer rigorous approximation guarantees.This proposal aims at leveraging the significant potential of our novel approach to yield further progress. We seek to achieve the following three goals in 2028: (1) quantitative verification of robustness for a binarized neural network with one million neurons, (2) rigorous resilience of critical infrastructures such as the power grid of cities of the size of Los Angeles, and (3) software reliability and coverage analysis for programs with 10K lines of code. Achieving these goals would necessitate algorithmic innovations that can take advantage of the underlying structure in real-world problem instances, develop data-driven solver design, and utilize new architectures.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2024-05956
Name nom
Meel, Kuldeep Singh
Department département
Computer Science
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
36000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2803
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Knowledge representation
Research subject fr
Répresentation des connaissances
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Scalable Next Generation Automated Reasoning Techniques
Keywords
automated reasoning; constrained counting; constrained sampling; functional synthesis; constraint satisfaction; hashing-based methods; boolean satisfiability; knowledge compilation
Application summary
This project focuses on the development of scalable automated symbolic reasoning techniques and their integration with statistical reasoning methods to enable the development of provably robust, reliable, and trustworthy computing systems. The current generation of symbolic reasoning techniques excel at qualitative tasks; such techniques sufficed for traditional systems whose design sought to achieve deterministic behavior. In contrast, modern computing systems crucially rely on statistical methods to account for the uncertainty in the environment and to reason about the behavior of these systems. The proposed research program will focus on developing the next generation of automated reasoning techniques that can perform higher-order tasks such as quantitative measurement, sampling of representative behavior, and automated synthesis of systems. From a core technical perspective, the project builds on the SAT revolution, which refers to algorithmic advances in combinatorial solving techniques for the fundamental problem of satisfiability (SAT), i.e., whether it is possible to satisfy a given set of constraints. The SAT revolution offers the opportunity to develop scalable techniques for problems that lie beyond SAT from a complexity perspective and, therefore, stand to benefit from the availability of powerful SAT engines. Our project seeks to enable a Beyond SAT revolution via the design of scalable techniques for two fundamental problems that lie beyond SAT: Constrained counting and constrained sampling, In constrained counting, the task is to count the total weight, subject to a given weight function, of the set of solutions of input constraints. In constrained sampling, the task is to sample randomly, subject to a given weight function, from the set of solutions. Even the approximate variants of these problems are known to be computationally intractable, and therefore, despite strong theoretical and practical interest over the years, there is still an immense gap between theory and practice. Our recent work in counting and sampling has yielded dramatic progress. By combining the ideas of using SAT solving as an oracle and the reduction of the solution space via universal hashing, we have developed highly scalable algorithms that offer rigorous approximation guarantees.This proposal aims at leveraging the significant potential of our novel approach to yield further progress. We seek to achieve the following three goals in 2028: (1) quantitative verification of robustness for a binarized neural network with one million neurons, (2) rigorous resilience of critical infrastructures such as the power grid of cities of the size of Los Angeles, and (3) software reliability and coverage analysis for programs with 10K lines of code. Achieving these goals would necessitate algorithmic innovations that can take advantage of the underlying structure in real-world problem instances, develop data-driven solver design, and utilize new architectures.