**Speaker:** Claudio Chamon (BU)

**When:** Oct 12th 12:30 pm

**Where: **PAB421

**Abstract:** We explore a link between complexity and physics for circuits of given

functionality. Taking advantage of the connection between circuit

counting problems and the derivation of ensembles in statistical

mechanics, we tie the entropy of circuits of a given functionality and

fixed number of gates to circuit complexity. We use thermodynamic

relations to connect the quantity analogous to the equilibrium

temperature to the exponent describing the exponential growth of the

number of distinct functionalities as a function of complexity. This

connection is intimately related to the finite compressibility of

typical circuits. Finally, we use the thermodynamic approach to

formulate a framework for the obfuscation of programs of arbitrary

length — an important problem in cryptography — as thermalization

through recursive mixing of neighboring sections of a circuit, which can

viewed as the mixing of two containers with “gases of gates”. This

recursive process equilibrates the average complexity and leads to the

saturation of the circuit entropy, while preserving functionality of the

overall circuit. The thermodynamic arguments hinge on ergodicity in the

space of circuits which we conjecture is limited to disconnected ergodic

sectors due to fragmentation. The notion of fragmentation has important

implications for the problem of circuit obfuscation as it implies that

there are circuits with same size and functionality that cannot be

connected via local moves. Furthermore, we argue that fragmentation is

unavoidable unless the complexity classes NP and coNP coincide.