Skip to content Skip to navigation
PhD Defense
9/26/2014 03:00 pm
CoRE B(Room 305)

New Computational Aspects of Discrepancy Theory

Aleksandar Nikolov, Rutgers University

Defense Committee: S. Muthukrishnan (chair), Michael Saks, Swastik Kopparty and Salil Vadhan (Harvard)

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, and communication complexity, among others. I will discuss recent examples of the interplay between discrepancy theory and computer science.

I will present positive and negative results on the approximability of classical notions of discrepancy, including the first hardness of approximation results for discrepancy and the first non-trivial approximation algorithms for hereditary discrepancy. The approximation algorithms are intimately related to a new application of discrepancy theory to private data analysis. This connection has led to a characterization of the necessary and sufficient error to answer an arbitrary load of counting queries under differential privacy. The tools developed for these results have also led to progress on a number of long-standing questions in discrepancy theory, such as the discrepancy of arithmetic progressions and of axis-aligned boxes.