Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Colloquia Archive 
 Postdoc Seminars Archive 
 Quantum Lunch 
 Quantum Lunch Archive 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 P/T Colloquia 
 Kac Lectures 
 Kac Fellows 
 Dist. Quant. Lecture 
 Ulam Scholar 
 CNLS Fellowship Application 
 Student Program 
 Past Visitors 
 History of CNLS 
 Maps, Directions 
 CNLS Office 
Thursday, July 12, 2012
10:00 AM - 11:30 AM
CNLS Conference Room (TA-3, Bldg 1690)


Phase Transitions, Circuit Complexity, and Sampling for Parity, Majority and Random Functions

Simon DeDeo
Omidyar Fellow Santa Fe Institute

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,