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.