BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Symmetric Arithmetic Circuits - Gregory Wilsenach\, University of 
 Cambridge
DTSTART:20201030T140000Z
DTEND:20201030T150000Z
UID:TALK152587@talks.cam.ac.uk
CONTACT:Jamie Vicary
DESCRIPTION:https://youtu.be/8B4qZ6KLdqA\n\nA large number of algebraic pr
 oblems can be reduced to the problem of computing families of polynomials.
  We conventionally model these computations using arithmetic circuits. The
  central question in the subject\, an algebraic analogue of the P vs NP pr
 oblem\, asks whether there is a super-polynomial lower bound on the sizes 
 of circuits computing the permanent. We introduce symmetric arithmetic cir
 cuits\, i.e. arithmetic circuits with a natural symmetry restriction. In t
 he context of circuits computing polynomials defined on a matrix of variab
 les\, such as the determinant or the permanent\, the restriction amounts t
 o requiring that the shape of the circuit is invariant under row and colum
 n permutations of the matrix. We establish unconditional exponential\, low
 er bounds on the size of any symmetric circuit for computing the permanent
  over any field of characteristic other than 2. In contrast\, we show that
  there are polynomial-size symmetric circuits for computing the determinan
 t over fields of characteristic zero.
LOCATION:Online
END:VEVENT
END:VCALENDAR