BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1731
DTSTAMP:20260609T111002Z
SUMMARY:Deterministic Algorithms for Low Individual Degree Factors of Spars
 e Polynomials
DESCRIPTION:Speaker: Rishabh Kothary (University of Toronto)\n\nAbstract: \
 nPolynomial factorization is a central problem in computational algebra an
 d algebraic complexity\, with connections to many areas in theoretical co
 mputer science. Even for the case of sparse multivariate polynomials there
  is a lot we do not understand- we only know subexponential time determini
 stic factoring algorithms for sparse polynomials by the recent work of Bha
 ttacharjee\, Kumar\, Rai\, Ramprasad and Saraf. In the case where the inpu
 t sparse polynomial has constant individual degree\, we know how to factor
  deterministically in quasipolynomial time by the work of Bharagava\, Sara
 f and Volkovich and a recent improvement by Chuyoon and Shpilka.\nIn this 
 work we give a deterministic polynomial time algorithm that takes as input
  a sparse polynomial of constant individual degree and outputs a list of c
 ircuits such that every factor of the input is in the list. One caveat is 
 that the list might contain additional spurious circuits that are not fact
 ors.\nWe also give a quasipolynomial time deterministic algorithm that tak
 es as input a general sparse polynomial and outputs a list of circuits su
 ch that every factor of the input of constant individual degree is in the 
 list. Again the list might contain additional spurious circuits. A conseq
 uence of our algorithm is a new upper bound on the total number of  bound
 ed individual degree factors of a sparse polynomial.\nThis is based on joi
 nt work with Somnath Bhattacharjee (U of T)\, Shanthanu S. Rai (TIFR) and 
 Shubhangi Saraf (U of T).\nBio: Rishabh Kothary is a second year PhD stud
 ent at University of Toronto being advised by Swastik Kopparty and Shubhan
 gi Saraf. He is interested in coding theory and algebraic complexity.\n
URL:https://www.tcs.tifr.res.in/web/events/1731
DTSTART;TZID=Asia/Kolkata:20260610T160000
DTEND;TZID=Asia/Kolkata:20260610T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR