BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/620
DTSTAMP:20230914T125931Z
SUMMARY:A Deterministic Polynomial Time Algorithm for Word Problem Over the
  Free Skew Field
DESCRIPTION:Speaker: Ankit Garg (Princeton University\nDepartment of Comput
 er Science\n35\, Olden Street\nPrinceton\, NJ 08544\nUnited States of Amer
 ica)\n\nAbstract: \nAbstract: We study the word problem for the free skew 
 field of non-commutative rational functions. We prove that an existing alg
 orithm due to Gurvits is actually a deterministic polynomial time algorith
 m for this problem (over the rationals). Our analysis is simple\, providin
 g explicit bounds on the ``capacity'' measure of totally positive operator
 s introducted by Gurvits.\n\nThis problem has a rich history and has appea
 red in various forms in a remarkable number of mathematical and computatio
 nal areas. Besides non-commutative algebra\, it also has various connectio
 ns to computational complexity and de-randomization\, commutative invarian
 t theory\, quantum information theory\, system theory\, automata and langu
 age theory. I plan to explain some of these connections\, as well as the c
 entral open problem relating them - the ``fullness dimension''.\n\nNo spec
 ial background will be assumed\, as it can be\, the problem\, algorithm an
 d analysis can be framed in the language of linear algebra (this is joint 
 work with Rafael Oliveira and Avi Wigderson).\n \n
URL:https://www.tcs.tifr.res.in/web/events/620
DTSTART;TZID=Asia/Kolkata:20150825T160000
DTEND;TZID=Asia/Kolkata:20150825T170000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR