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

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)

*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)

Building: | East Hall |
---|---|

Event Type: | Workshop / Seminar |

Tags: | Mathematics |

Source: | Happening @ Michigan from Department of Mathematics, Department of Physics, Michigan Center for Applied and Interdisciplinary Mathematics |