Skip to Content

Search: {{$root.lsaSearchQuery.q}}, Page {{$root.page}}

MCAIM Colloquium Seminar

Symmetric Models of Computation
Wednesday, October 12, 2022
3:00-4:00 PM
4448 East Hall Map
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)
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