Aleksandar Nikolov, B.S.

Aleksandar Nikolov is a Ph.D. student in the Department of Computer Science at Rutgers University. He finished his undergraduate studies at St. Peter’s University, New Jersey. His research area is discrepancy theory and its applications. In particular, his work develops new methods for computational aspects of discrepancy theory, and its applications to differential privacy and its extensions. He has published in top conferences of theoretical computer science such as FOCS, STOC, SODA and PODS. For disproving József Beck’s ‘three permutations’ conjecture with Alantha Newman, open since 1984, Joel Spencer awarded them $100 for this solution, and the result will appear in the forthcoming FOCS 2012 conference. With S. Muthukrishnan, he exhibited a connection between the error complexity of differentially private algorithms and combinatorial discrepancy, which leads to new tight upper and lower error bounds for privately computing natural range counting queries. This result was published in STOC 2012. Earlier, with Moses Charikar and Alantha Newman, he proved tight hardness results for approximating discrepancy. Their work exhibited a connection between the hardness of approximating discrepancy and lower bounds for discrepancy. This result appeared in SODA 2011. Alex has also work on extensions of differential privacy, such as pan-privacy, with results that appeared in PODS.

Subscribe to MPS announcements and other foundation updates