BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1340
DTSTAMP:20231031T062211Z
SUMMARY:Black-Box Identity Testing of Noncommutative Rational Formulas in D
eterministic Quasipolynomial Time
DESCRIPTION:Speaker: Abhranil Chatterjee (Indian Statistical Institute\, Ko
lkata)\n\nAbstract: \nRational Identity Testing (RIT) is the decision prob
lem of determining whether or not a given noncommutative rational formula
computes zero in the free skew field. It admits a deterministic polynomial
-time white-box algorithm [Garg et al.\, 2016\; Ivanyos et al.\, 2018\; Ha
mada and Hirai\, 2021]\, and a randomized polynomial-time black-box algori
thm [Derksen and Makam\, 2017] via singularity testing of linear matrices
over the free skew field.Designing a subexponential-time deterministic RIT
algorithm in black-box is a major open problem in this area. Despite bein
g open for several years\, this question has seen very limited progress. I
n fact\, the only known result in this direction is the construction of a
quasipolynomial-size hitting set for rational formulas of only inversion h
eight two [Arvind et al.\, 2022].In this talk\, I'll present my recent wor
k where we significantly improve the black-box complexity of this problem
and obtain the first quasipolynomial-size hitting set for all rational fo
rmulas of polynomial size. Our construction also yields a quasi-NC RIT al
gorithm in the white-box setting.\n \nJoint work with V. Arvind (IMSc) an
d Partha Mukhopadhyay (CMI).\n
URL:https://www.tcs.tifr.res.in/web/events/1340
DTSTART;TZID=Asia/Kolkata:20231107T160000
DTEND;TZID=Asia/Kolkata:20231107T173000
LOCATION:via Zoom in A201
END:VEVENT
END:VCALENDAR