BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260530T210537Z
UID:Seminar-ACTO-1091@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nikhil Mande:MAILTO:Nikhil.Mande@liverpool
DTSTART:20200722T140000
DTEND:20200722T150000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:Abhiroop Sanyal: On Algebraic Branching Programs of Small Width\n\nIn 1979, Valiant showed that the complexity class VPe of families with polynomially bounded formula size is contained in the class VPs of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes, we study the topological closure VPe, i.e., the class of polynomials that can be approximated arbitrarily closely by polynomials in VPe. We describe VPe using the well-known continuant polynomial (in characteristic different from 2). Further understanding this polynomial seems to be a promising route to new formula size lower bounds.\n\nOur methods are rooted in the study of ABPs of small constant width. In 1992, Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of VPe. As a natural continuation of this work, we prove that the class VPN can be described as the class of families that admit a hypercube summation of polynomially bounded dimension over a product of polynomially many affine linear forms. This gives the first separations of algebraic complexity classes from their nondeterministic analogs.\n\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1091
LOCATION:Online MT CSACTOO365Team
END:VEVENT
END:VCALENDAR