BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/918
DTSTAMP:20230914T125943Z
SUMMARY:On the Structure and Lower Bounds for Multilinear Branching Program
 s
DESCRIPTION:Speaker: Ramya C. (Ph.D. student\nDepartment of Computer\nScien
 ce and Engineering\nIIT Madras)\n\nAbstract: \nAbstract: Polynomials are t
 he most fundamental mathematical objects in algebra and it is compelling t
 o understand the complexity of computing polynomials. That is\, given a p
 olynomial we want to understand the number of arithmetic operations needed
  to compute it. Leslie G. Valiant introduced the notion of arithmetic cir
 cuits as a model for  computing polynomials. We will primarily be interes
 ted in size of an arithmetic circuit computing f which is the number of a
 rithmetic operations needed to compute the polynomial f.  Further\, Valia
 nt conjectured that the permanent of an nxn matrix viewed as a polynomial
  cannot be computed by arithmetic circuits  of size polynomial in n. Subs
 equent to Valiant's conjecture\, proving size  lower bounds for circuits
  computing permanent have been of much interest. While the answer to Valia
 nt's conjecture seems to be at a distance\, the focus has been on restric
 ted classes of circuits.\nIn this talk\, we will focus on Algebraic Branch
 ing Programs\, yet another model for computing polynomials. Interesting po
 lynomial families such as determinant\, permanent etc. being multilinear\
 , it is natural to consider syntactic multilinear Algebraic Branching Prog
 rams(smABPs) where every variable appears as an edge label at most once a
 long any path in the branching program. The best known size lower bound fo
 r smABPs is barely quadratic in the number of variables. Proving super-po
 lynomial size lower bounds for smABPs computing an explicit multilinear po
 lynomial is a challenging problem in Algebraic Complexity Theory.\nIn thi
 s talk\, we aim to understand the structure of smABPs and outline possible
  approaches to prove super-polynomial lower bounds for smABPs. We obtain 
 a new decomposition theorem  for  smABPs: We show that  any n-variate p
 olynomial that can be computed by an smABP of size S\, can be written as 
 a sum of O(S) many multilinear polynomials where each summand is a product
  of two polynomials in at most 2n/3 variables\, computable by smABPs. As 
 an immediate corollary to our decomposition theorem for smABPs\, we obtain
  a low bottom fan-in version of the depth reduction by Tavenas[MFCS\, 2013
 ] for the case of smABPs.  This also leaves us with certain structural o
 bservations on smABPs which may be exploited to obtain super-polynomial lo
 wer bounds for smABPs. This is joint work with B.V.Raghavendra Rao\, IIT 
 Madras.\n
URL:https://www.tcs.tifr.res.in/web/events/918
DTSTART;TZID=Asia/Kolkata:20181121T160000
DTEND;TZID=Asia/Kolkata:20181121T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR