Left arrow Barnard.edu
Left arrow Barnard.edu
Search All of Barnard.edu
Events
Mar 3

Computer Science Seminar: Ilya Volkovich (University of Michigan)

-
Milstein Center 402
  • Add to Calendar 2020-03-03 10:00:00 2020-03-03 11:00:00 Computer Science Seminar: Ilya Volkovich (University of Michigan) Speaker: Ilya Volkovich, University of Michigan Title: Algebraic problems: the frontier of efficient randomized computation Randomness is a valuable resource in many computational tasks. Indeed, the security and/or the accuracy of many randomized algorithms and protocols rely on the random bits being truly random and independent. However, in practice such random bits are elusive, which may compromise the performance of the underlying systems. This motivates the following fundamental question:- 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. Time permitting, I will also discuss the problems I have been working on and some recent connections to cryptography and machine learning. Dr. Ilya Volkovich is a Senior Lecturer in the Department of Computer Science and Engineering at the University of Michigan, where he has taught courses in the theory of computation for several years. Previously, he was a Postdoctoral Research Associate in the Computer Science Department at Princeton University and held a visiting position at the Institute of Advanced Study. In 2012, he obtained his Ph.D. in Computer Science from Technion, Israel Institute of Technology, advised by Prof. Amir Shpilka. His research interests are in the broad area of theoretical computer science and discrete mathematics. More specifically, he is interested in aspects of algebraic complexity, randomness in computation, computational learning theory, and their applications to cryptography and machine learning.    Milstein Center 402 Barnard College barnard-admin@digitalpulp.com America/New_York public
  • Campus Map

Speaker: Ilya Volkovich, University of Michigan
Title: Algebraic problems: the frontier of efficient randomized computation

Randomness is a valuable resource in many computational tasks. Indeed, the security and/or the accuracy of many randomized algorithms and protocols rely on the random bits being truly random and independent. However, in practice such random bits are elusive, which may compromise the performance of the underlying systems. This motivates the following fundamental question:-

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. Time permitting, I will also discuss the problems I have been working on and some recent connections to cryptography and machine learning.

Dr. Ilya Volkovich is a Senior Lecturer in the Department of Computer Science and Engineering at the University of Michigan, where he has taught courses in the theory of computation for several years. Previously, he was a Postdoctoral Research Associate in the Computer Science Department at Princeton University and held a visiting position at the Institute of Advanced Study. In 2012, he obtained his Ph.D. in Computer Science from Technion, Israel Institute of Technology, advised by Prof. Amir Shpilka. His research interests are in the broad area of theoretical computer science and discrete mathematics. More specifically, he is interested in aspects of algebraic complexity, randomness in computation, computational learning theory, and their applications to cryptography and machine learning. 

 

Computer Science