BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1444
DTSTAMP:20240812T061508Z
SUMMARY:Exponential lower bounds via Exponential sums
DESCRIPTION:Speaker: Somnath Bhattacharjee (Chennai Mathematical Institute)
\n\nAbstract: \nValiant's famous VP vs. VNP conjecture states that the sym
bolic permanent polynomial does not have polynomial-size algebraic circuit
s. However\, the best upper bound on the size of the circuits computing th
e permanent is exponential. Informally\, VNP is an exponential sum of VP-c
ircuits. In this paper we study whether\, in general\, exponential sums of
algebraic circuits require exponential-size algebraic circuits. We show t
hat the famous Shub-Smale tau-conjecture indeed implies such an exponentia
l lower bound for an exponential sum. Our main tools come from parameteriz
ed complexity. Along the way\, we also prove an exponential fpt (fixed-par
ameter tractable) lower bound for the parameterized algebraic complexity c
lass VW[P]\, weighted sum circuits (constant-free\, unbounded degree)\, as
suming the same conjecture. VW[P] can be thought of as the weighted sums o
f (unbounded-degree) circuits\, where only +1/-1 constants are cost-free.
To the best of our knowledge\, this is the first time the Shub-Smale tau-c
onjecture has been applied to prove explicit exponential lower bounds. Fur
thermore\, we prove that when this class is fpt\, then a variant of the co
unting hierarchy\, namely the linear counting hierarchy collapses. Moreove
r\, if a certain type of parameterized exponential sums is fpt\, then inte
gers\, as well as polynomials with coefficients being definable in the lin
ear counting hierarchy have subpolynomial tau-complexity. Finally\, we sho
wed a completeness result on a subclass VW[F] (weighted sum of formulas)\n
\nThis talk is based on joint work with Markus Blaser (University of Saa
rland)\, Pranjal Dutta (NUS) and Saswata Mukherjee (NUS) [ICALP 2024]\, li
nk: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024
.24\n \nShort Bio:\nSomnath completed his Bachelors and Masters from the
Chennai Mathematical Institute and is on his way to the University of Toro
nto for his PhD. His current research interests are in algorithms and comp
lexity with a focus on problems with an algebraic flavor\, including algeb
raic complexity\, algebraic algorithms\, pseudorandomness\, algebraic proo
f complexity and error correcting codes.\n
URL:https://www.tcs.tifr.res.in/web/events/1444
DTSTART;TZID=Asia/Kolkata:20240819T160000
DTEND;TZID=Asia/Kolkata:20240819T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR