 |
Center for Nonlinear Studies |
Acyclic Boolean circuits are not only central to problems in machine learning, such as causal inference in the Pearl model, but they also form the base set of computational complexity classes in theoretical computer science. A deeper understanding of the structure of the space of possible circuits, as increasingly stringent constraints are put on expectation values of the ensemble, is key to understanding both limits on the ability to search that space (for inference on real-world systems), and on the origins of some of the few positive (i.e., non-inclusion) results in computational complexity theory. In pursuit of that dual goal, I describe recent collaborative work investigating the structure of random Boolean circuits. I describe Markov Chain methods for how to sample from (the ensemble generalization) of standard computational complexity classes such as Nick's Class (NC), as well as the full space of (labelled) circuits. I then show the emergence of two kinds of transitions between an ordered and disordered phase for Parity: in the case of the XOR basis, we find a crossover, or Fermi-like, transition, while the case of the NAND we find a more complicated structure for the partition function which is compatible with the existence of a true phase transition in the thermodynamic limit. We conclude by conjecturing the existence of an order parameter to determine the order of the latter transition, and report recent results for Majority and for the space of random functions.
Host: Aric Hagberg, CNLS, 667-1444, hagberg@lanl.gov