Anuj Dawar Circuit Lower Bounds Assuming Symmetry, Big Seminar
It is our pleasure to share the Big Seminar talk by Anuj Dawar Circuit Lower Bounds Assuming Symmetry . Abstract: It is a longstanding open question in complexity theory to show that the permanent of a matrix cannot be computed by a polynomialsize 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 gamebased lowerbound 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. Seminars schedule and archive are available here
|
|