BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1421
DTSTAMP:20240521T095047Z
SUMMARY:Lower Bounds for Planar Arithmetic Circuits
DESCRIPTION:Speaker: Ramya C. (The Institute of Mathematical Sciences)\n\nA
bstract: \nArithmetic circuits are a natural computational model for compu
ting multivariate polynomials over a field. Planar arithmetic circuits are
circuits whose underlying graph is planar. The size of a circuit which
is the number of vertices in the underlying graph is a fundamental paramet
er concerning circuits. In this talk\, we will prove a superlinear lower
bound on the size of planar arithmetic circuits computing an explicit bil
inear form. More generally\, we will walk-through the algebraic complexity
of bilinear forms. Furthermore\, Baur and Strassen(1983) showed that all
the first order partial derivatives of a polynomial can be simultaneously
computed with only a constant factor blow-up in size. We observe that an a
nalogous statement does not hold in the case of planar circuits.\nThis tal
k is based on joint work with Pratik Shastri(IMSc).\nShort Bio:\nRamya is
currently a faculty member in the Theoretical Computer Science group at th
e Institute of Mathematical Sciences(IMSc)\, Chennai.Prior to this\, she w
as a faculty member at the Chennai Mathematical Institute(CMI). Before joi
ning CMI\, she was a postdoctoral fellow at STCS\, TIFR\, Mumbai during
2019-2021.She obtained her PhD from IIT Madras in 2019. Her research is ce
ntered around Computational Complexity Theory\, particularly problems with
an algebraic flavor.\n
URL:https://www.tcs.tifr.res.in/web/events/1421
DTSTART;TZID=Asia/Kolkata:20240611T160000
DTEND;TZID=Asia/Kolkata:20240611T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR