On Randomness and Fast Sorting in Theory and Practice

Sorting is the most fundamental problem for a list of elements. But how fast can we sort?

I will start the talk by presenting my research interests which includes the study of the role of randomness in computation. Next, I will give a 15-20 minute undergraduate level lecture about sorting algorithms. In particular, we will see the fastest in theory and even faster in practice sorting algorithms, when the later is achieved using randomness. Finally, I will discuss my teaching philosophy that we, as teachers, should never stop learning.
Ilya Volkovich is a Postdoctoral Visiting Scholar and a Lecturer in the Department of Electrical Engineering and Computer Science, University of Michigan. Last Fall, he was also a Lecturer in the Mathematics Department. Previously, Ilya was a Postdoctoral Research Associate and a Lecturer in the Computer Science Department at Princeton University and held a visiting position at the Institute of Advanced Study.

His research interests focus on Theoretical Computer Science, Discrete Mathematics and Algorithms with a particular emphasis on Computational Complexity, Derandomization, Algebraic Complexity and the Application of Algebraic Tools to Algorithms.

In 2012, Ilya graduated from the Computer Science Department of the Technion in Haifa where he did his Ph.D. under the supervision of Prof. Amir Shpilka.