UCLA

Knowledge compilation is concerned with compiling problems encoded in some input language into some tractable, output language, with the goal of allowing one to solve such problems efficiently if the compilation is successful. This paradigm was originally motivated by the need to push much of the computational overhead into an offline compilation phase, which can then be amortized over a large number of queries in an online computation phase. In this dissertation, we study various new approaches to enhance the offline compilation phase, both theoretically and practically. We also study knowledge compilation from a perspective where it is employed as a general methodology for computation instead of just a paradigm that is concerned with the offline/online divide.

In particular, we introduce a hierarchy of complexity parameters to bound the sizes of compiled representations. These new parameters are based on incorporating the logical content of the input representations, as opposed to existing parameters (e.g., treewidth) that are only based on the structure of the input. Our results improve some of the best known upper bounds on the compilation of influential representations, such as DNNFs, SDDs, and OBDDs. Moreover, we develop two new practical compilation algorithms for the DNNF and SDD languages, leading to orders of magnitude faster compilations. Finally, we study solving Beyond-NP problems using knowledge compilation, while particularly extending the reach of knowledge compilation to tackling problems in the highly intractable complexity class PP^PP. Our results show the applicability of knowledge compilers as black-box tools for solving Beyond-NP problems, similar to the use of SAT solvers for solving NP-complete problems.