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