Anuj Dawar "Circuit Lower Bounds Assuming Symmetry"
Anuj Dawar from University of Cambridge will give the talk "Circuit Lower Bounds Assuming Symmetry" on the labs' Big Seminar.
Password: first 6 decimal places of $\pi$ after the decimal point
It is a long-standing open question in complexity theory to show that the permanent of a matrix cannot be computed by a polynomial-size arithmetic circuit. We proved an exponential lower bound on the size of any family of symmetric arithmetic circuits for computing the permanent. Here, symmetric means that the circuit is invariant under simultaneous row and column permutations of the matrix. In this talk, I will explain the game-based lower-bound methods and show how they can be used for deriving further lower bounds, varying symmetry groups and other matrix polynomials, such as the determinant.
Joint work with Gregory Wilsenach.
Everyone is invited to attend. The language of the lecture is English. The event is aimed at master and graduate students, as well as researchers in the field of combinatorics.