MCAIM Colloquium Seminar

Many well-studied Boolean functions {0,1}^n → {0,1} are naturally invariant under some group P acting on coordinates 1,…,n. For example, Graph Connectivity on m-vertex graphs, viewed as a function {0,1}^(m choose 2) → {0,1}, is invariant under the action of Sym(m). It is interesting to investigate the complexity of P-invariant functions in symmetric models of computation, where each state of a computation is itself a P-invariant object. In this talk, I will discuss results concerning two symmetric models: P-invariant Boolean circuits (joint work with William He) and the choiceless computation model of Blass-Gurevich-Shelah 1999.

Talk in person in East Hall 4448 and on Zoom:

Join Zoom Meeting:
https://umich.zoom.us/j/94775967057

Meeting ID: 947 7596 7057 Speaker(s): Benjamin Rossman (Duke University)