On Scaling Knowledge Compilation Applications
A/P Meel Kuldeep S., University of Toronto
COM3 Level 2
MR21, COM3 02-61
Abstract:
Knowledge compilation is a core area of computer science, serving as the foundation for tools that perform model counting and sampling tasks, which are widely applied across various domains. As the scalability of these tools is crucial for practical applications, it is essential to consider how to optimize knowledge compilation techniques for practical use. There have been numerous efforts, mainly through the introduction of more succinct knowledge compilation forms and better heuristics. In this thesis, we will present our framework for thinking about scalability in knowledge compilation applications, offering a different perspective on designing more efficient knowledge compilation applications.
The framework takes an orthogonal approach to existing efforts in scaling knowledge compilation, emphasizing that additional scalability can be achieved by jointly optimizing both the underlying knowledge compilation techniques and the specific applications they serve. In particular, the framework introduces three key perspectives on scalability: (a) Can we use the knowledge compilation forms more efficiently? (b) Are there opportunities for relaxations? (c) Are there alternative ways to more concisely describe the problem? In this talk, we will illustrate each perspective using approaches and tools developed over a series of works, with more emphasis on (c).