Anuj Dawar “Circuit Lower Bounds Assuming Symmetry” | Big Seminar

April 8, 2021
19.00 MSK (UTC +3)

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.

The talk will be held in zoom
Meeting ID: 279-059-822 zoom-link
Password: first 6 decimal places of $\pi$ after the decimal point

You can also write to Alexander Polyanskii (alexander.polyanskii@yandex.ru) or to Maksim Zhukovskii (zhukmax@gmail.com) if you want to be added to mailing list.

Abstract:

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.

Watch the video:

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.