Spring 2021

Beyond NP with Tractable Circuits

Tuesday, March 9th, 2021 8:30 am10:30 am

Add to Calendar


Adnan Darwiche (UCLA)



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.