Abstract
Tractable circuits are Boolean or Arithmetic circuits that satisfy certain properties which allow them to compute some hard queries in polynomial time, including ones belonging to complexity classes that are beyond NP. The theory of tractable circuits provides a systematic computational framework as it streamlines algorithmic work into a process of enforcing circuit properties, known also as the process of “Knowledge Compilation.” In this talk, I will discuss the theory of tractable circuits, including circuit properties and the foundations of knowledge compilers. I will particularly emphasize tractable circuits that are relevant to probabilistic reasoning, machine learning and explainable AI while hinting at some open problems that will help advance the theory further.