A common theme of my research is the connections between high-dimensional geometry and computer science. I have been developing geometric methods for designing algorithms in private data analysis. I am also interested in discrepancy theory, a mathematical field studying how uniform discrete objects can be. It has natural connections to discrete and convex geometry, numerical integration and number theory, but also many surprising applications in computer science, including private data analysis, and approximation algorithms. More recently, I have been interested in computational questions in high-dimensional geometry, such as near neighbor search, and geometric optimization problems. Some of the geometric optimization questions I study are closely related to questions in experimental design. I am also interested in efficient algorithms for massive data, in particular streaming algoritms and parallel algorithms. Below you can find some of my work in these areas:
[arXiv] Vivek Madan, Aleksandar Nikolov, Mohit Singh, Uthaipon Tantipongpipat, Maximizing Determinants under Matroid Constraints, to appear in FOCS 2020.
[arXiv] Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, Zhiwei Steven Wu, Private Query Release Assisted by Public Data, ICML 2020.
[arXiv] Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, Huanyu Zhang, Locally Private Hypothesis Selection, COLT 2020.
[arXiv] Alexander Edmonds, Aleksandar Nikolov, Jonathan Ullman, The Power of Factorization Mechanisms in Local and Central Differential Privacy, STOC 2020.
[arXiv] Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh, Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems, SODA 2020. Invited to the Special Issue.
[arXiv] Andrey Boris Khesin, Aleksandar Nikolov, Dmitry Paramonov, Preconditioning for the Geometric Transportation Problem , SoCG 2019. Invited to the Special Issue.
[arXiv] Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten, On Mean Estimation for General Norms with Statistical Queries, COLT 2019.
[arXiv] Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke, Towards Instance-Optimal Private Query Release, SODA 2019.
[arXiv] Aleksandar Nikolov, Mohit Singh, Uthaipon Tao Tantipongpipat, Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design, SODA 2019.
[Slides] Daniel Dadush, Aleksandar Nikolov, Kunal Talwar, Nicole Tomczak-Jaegermann, Balancing Vectors in Any Norm, FOCS 2018.
[arXiv] Christoph Aistleitner, Dmitriy Bilyk, Aleksandar Nikolov, Tusnady's problem, the transference principle, and non-uniform QMC sampling, MCQMC 2016.
[arXiv] Alexandr Andoni, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten, Approximate Near Neighbors for General Symmetric Norms, STOC 2017.
[arXiv] Assimakis Kattis, Aleksandar Nikolov, Lower Bounds for Differential Privacy from Gaussian Width, SoCG 2017.
[ToC] [arXiv] [Extended Abstract] [Talk] Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandar Nikolov, Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem, APPROX-RANDOM 2016. Full version in the ToC Special Issue on APPROX-RANDOM 2016. Theory of Computing 15 (2019), pp 1-58.
[PDF] Aleksandar Nikolov, Mohit Singh, Maximizing Determinants under Partition Constraints, 2016 ACM Symposium on Theory of Computing (STOC 2016).
[arXiv] Aleksandar Nikolov, An Improved Private Mechanism for Small Databases, 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), Track A.
[arXiv] Aleksandar Nikolov, Randomized Rounding for the Largest j-Simplex Problem, 2015 ACM Symposium on Theory of Computing (STOC 2015).
- [arXiv] Jiri Matousek, Aleksandar Nikolov, Combinatorial Discrepancy for Boxes via the Ellipsoid-Infinity Norm, 2015 Symposium on Computational Geometry (SoCG 2015). Best Paper Award. In the final version the "ellipsoid-infinity norm" terminology was replaced by the standard gamma-2 factorization norm.
- [arXiv] [Slides] Aleksandar Nikolov, Kunal Talwar, Approximating Hereditary Discrepancy via Small Width Ellipsoids, 2015 SIAM Symposium on Discrete Algorithms (SODA 2015).
[arXiv] [Class Notes (Big Data, Harvard, Fall 2013)] Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev, Parallel Algorithms for Geometric Graph Problems, 2014 ACM Symposium on Theory of Computing (STOC 2014).
[DCG] [arXiv] Cynthia Dwork, Aleksandar Nikolov, Kunal Talwar, Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations, 30th Annual Symposium on Computational Geometry (SoCG 2014). Full version in DCG Special Issue on SoCG 2014. Discrete and Computational Geometry, 53 (2015), no.3.
[arXiv] Aleksandar Nikolov, The Komlos Conjecture Holds for Vector Colorings, unpublished.
[SICOMP] [arXiv] [Slides] Aleksandar Nikolov, Kunal Talwar, Li Zhang, The Geometry of Differential Privacy: the Approximate and Sparse Cases, 2013 ACM Symposium on Theory of Computing (STOC 2013). Full version in SICOMP Special Issue on STOC 2013. SIAM J. Comput., 45(2), 575-616.
[arXiv] Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov, Nearly Optimal Private Convolution, European Symposium on Algorithms (ESA 2013).
[arXiv] Jean Bolot, Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov, Nina Taft, Private Predicate Sums on Decayed Streams, to appear in 16th International Conference on Extending Database Technology (ICDT 2013).
[PDF] Alantha Newman, Ofer Neiman, Aleksandar Nikolov, Beck's Three Permutations Conjecture: a Counterexample and Some Consequences, 53rd Symposium on Foundations of Computer Science (FOCS 2012)
[arXiv] Darakhshan Mir, S. Muthukrishnan, Aleksandar Nikolov, Rebecca Wright, Pan-private Algorithms via Statistics on Sketches, 2011 ACM Symposium on Principles of Database Systems (PODS 2011).
[PDF] Aleksandar Nikolov, Shenzhi Li, William M. Pottenger, Privacy-Enhancing Distributed Higher-Order ARM. Workshop on Link Analysis, Counterterrorism, and Security, SDM 2009.