Seminars & Colloquia
Ilya Volkovich
University of Michigan
"Computer Algebra Algorithms: The Frontier of Efficient Randomized Computation"
Thursday March 21, 2019 09:30 AM
Location: 3211, EB2 NCSU Centennial Campus
(Visitor parking instructions)
Can every computational task that requires randomness be carried out deterministically, paying, perhaps only a small overhead?
Meanwhile, the nature of many algebraic problems makes them amenable to randomized algorithms. For example: a random set of vectors is independent, a random assignment to a low-degree polynomial is non-zero etc. Thus, you can easily find a set of independent vectors and a non-zero assignment by picking them uniformly at random. Indeed, it is not surprising that the frontier of efficient randomized computation consists of algebraic problems. Among the frontier problems are Polynomial Identity Testing, Polynomial Factorization and others.
In this talk I will discuss my research on the relationship between randomness, computation and algebra. I will also discuss the problems I have been working on and, if time permits, some recent connections to cryptography and machine learning.
Host: Blair Sullivan, CSC