Benjamin Rossman: Symmetric models of computation

Abstract

Many well-studied Boolean functions {0,1}^n → {0,1} are naturally invariant under some group P acting on coordinates 1,…,n. For example, the Perfect Matching function on m-node graphs is invariant under the action of Sym(m) on n = (m choose 2) edge-indicator coordinates. It is interesting to study the complexity of P-invariant functions in "symmetric" models of computation, where each state of a computation (e.g. layer of a circuit) is itself invariant under the action of P. This talk will survey results in two symmetric models: invariant AC^0 formulas for products of permutation matrices (joint work with William He) and the *choiceless* computation model of Blass-Gurevich-Shelah.