Аннотация:
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.
