Speaker: Aleksander Nikolov, Rutgers University

Title: Discrepancy Theory in Computer Science

Abstract:

Discrepancy theory studies how well discrete objects can approximate continuous ones. It has numerous applications throughout mathematics and computer science, including numerical analysis, computational geometry, communication complexity, among others. I will discuss recent examples of the interplay between discrepancy theory and computer science.

I will focus on a tight connection between hereditary discrepancy and private data analysis. In private data analysis the connection has led to a characterization of the necessary and sufficient error to privately answer an arbitrary load of counting queries. In discrepancy theory, the connection led to the first non-trivial efficient approximation of hereditary discrepancy, which arises in constructions of epsilon nets, rounding algorithms, among other applications.

There are potential directions to explore in the future in discrepancy theory and its applications to Complexity Theory, Statistics, Compressed Sensing and other areas.

Biography:

Aleksandar Nikolov is a graduating PhD Candidate at Rutgers University, working under the supervision of S. Muthukrishnan. He is broadly interested in theoretical computer science and algorithms, and specifically in discrepancy theory and its applications to computer science. He has worked on emerging applications of discrepancy theory to approximation algorithms for computationally hard problems, and to the theory of private data analysis. He is also interested in sublinear and parallel algorithms for massive data. He is a member of the inaugural group of Simons Graduate Fellows in Computer Science.

For additional information contact:

Vassos Hadzilacos