BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/876
DTSTAMP:20230914T125941Z
SUMMARY:Deterministic Factorization of Sparse Polynomials with Bounded Indi
 vidual Degree
DESCRIPTION:Speaker: Vishwas Bhargava (Rutgers University\nNew Brunswick-Pi
 scataway\nNew Jersey\nUnited States)\n\nAbstract: \nWe study the problem o
 f deterministic factorization of sparse polynomials. We show that if f \\i
 n \\F[x1\,…\,xn] is a polynomial with s monomials\, with individual degr
 ees of its variables bounded by d\, then f can be deterministically factor
 ed in time s^{O(\\poly(d)log n)}. Prior to our work\, the only efficient f
 actoring algorithms known for this class of polynomials were randomized\, 
 and other than for the cases of d=1 and d=2\, only exponential time determ
 inistic factoring algorithms were known.\nA crucial ingredient in our proo
 f is a quasi-polynomial sparsity bound for factors of sparse polynomials o
 f bounded individual degree. In particular we show if f is an s-sparse pol
 ynomial in n variables\, with individual degrees of its variables bounded 
 by d\, then the sparsity of each factor of f is bounded by s^{O(d^2 log n)
 }. This is the first nontrivial bound on factor sparsity for d>2. Our spa
 rsity bound uses techniques from convex geometry\, such as the theory of 
 Newton polytopes and an approximate version of the classical Caratheodory'
 s Theorem.\nOur work addresses and partially answers a question of von zur
  Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial boun
 d holds for the sparsity of factors of sparse polynomials.\nThis is joint 
 work with Shubhangi Saraf and Ilya Volkovich.\n
URL:https://www.tcs.tifr.res.in/web/events/876
DTSTART;TZID=Asia/Kolkata:20180528T160000
DTEND;TZID=Asia/Kolkata:20180528T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR