BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1376
DTSTAMP:20240103T041211Z
SUMMARY:How powerful are homogeneous algebraic formulas?
DESCRIPTION:Speaker: Prof. Nutan Limaye (IT University of Copenhagen)\n\nAb
 stract: \nProving explicit lower bounds on the size of algebraic formulas 
 is a long-standing open problem in the area of algebraic complexity theory
 . Recent results in the area have indicated a strategy for attacking this 
 question: show that we can convert a general algebraic formula to a homoge
 neous algebraic formula with moderate blow-up in size\, and prove strong l
 ower bounds against the latter model. In this talk we will discuss the fea
 sibility of the above strategy. Homogeneous formula lower bounds. We will 
 show lower bounds against ‘weighted’ homogeneous formulas of arbitrary
  depth. This is the first such lower bound for arbitrary depth formulas. T
 his gives a strong indication that lower bounds against homogeneous formul
 as may be within reach.Efficient homogenization. We show that any formula 
 F for a homogeneous polynomial of degree d can be homogenized over fields 
 of characteristic 0 as long as $d = s^{o(1)}$. Such a result was previousl
 y only known when $d = (\\log s)^{1+o(1)}$ (Raz (J. ACM (2013))).Non-commu
 tative homogenization. A recent result of Dutta\, Gesmundo\, Ikenmeyer\, J
 indal and Lysikov (2022) implies that to homogenize algebraic formulas of 
 any depth\, it suffices to homogenize non-commutative algebraic formulas o
 f depth just 3. We are able to show strong lower bounds against such homog
 enization\, suggesting barriers for this approach. The talk is based on a 
 joint work with Hervé Fournier\, Srikanth Srinivasan\, and Sébastien Tav
 enas. \n
URL:https://www.tcs.tifr.res.in/web/events/1376
DTSTART;TZID=Asia/Kolkata:20240105T143000
DTEND;TZID=Asia/Kolkata:20240105T153000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR