Theory Seminar
New Analysis of the Factor Refinement Algorithm with Applications
Aditya RaviUniversity of Micghian
WHEN:
Friday, December 4, 2020 @ 10:00 am - 11:00 am
This event is free and open to the publicAdd to Google Calendar
This event is free and open to the publicAdd to Google Calendar
WEB: Event Website
SHARE:
Abstract: In this talk I will discuss a new, simple characterization of the output of the Factor Refinement Algorithm, formally introduced and analyzed by Bach, Driscoll, and Shallit in 1993. Our characterization relies only on basic linear algebra. As applications, we obtain new relations between computing the square-free decomposition of an integer, Euler’s totient function, the radical of an integer, and some other multiplicative functions. While some of the above connections were already established in the literature, we believe that our contribution makes them simpler and more explicit.
Based on Joint work with Dr. Ilya Volkovich