Publications
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] Aleksandar Nikolov, Haohua Tang, Gaussian Noise is Nearly Instance Optimal for Private Unbiased Mean Estimation.
[arXiv] Aleksandar Nikolov, Private Query Release via the Johnson-Lindenstrauss Transform, SODA 2023.
Alexander Edmonds, Aleksandar Nikolov, Toniann Pitassi, On Learning versus Refutation in Noninteractive Local Differential Privacy, NeurIPS 2022.
[PDF] Lily Li, Evi Micha, Aleksandar Nikolov, Nisarg Shah, Partitioning Friends Fairly, AAAI 2023.
[arXiv] Deepanshu Kush, Aleksandar Nikolov, Haohua Tang, Near Neighbor Search via Efficient Average Distortion Embeddings, SoCG 2021. Invited to the Special Issue.
[SODA Proceedings] Alexandr Andoni, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten, Approximate Nearest Neighbors Beyond Space Partitions, SODA 2021.
[arXiv] Lily Li, Aleksandar Nikolov, On the Computational Complexity of Linear Discrepancy, ESA 2020.
[arXiv] Vivek Madan, Aleksandar Nikolov, Mohit Singh, Uthaipon Tantipongpipat, Maximizing Determinants under Matroid Constraints, 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] [TCS+ talk video] 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.
[JoCG] [arXiv] Andrey Boris Khesin, Aleksandar Nikolov, Dmitry Paramonov, Preconditioning for the Geometric Transportation Problem , SoCG 2019. Full version in the JoCG Special Issue on SoCG 2019. JoCG 11(2), 234-259, 2020.
[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.
[Math of OR] [arXiv] Aleksandar Nikolov, Mohit Singh, Uthaipon Tao Tantipongpipat, Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design, SODA 2019, Math of OR 47(2):847-877, 2022.
[Local copy] [Quanta Magazine] Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten, Hölder Homeomorphisms and Approximate Nearest Neighbors, FOCS 2018.
[PDF] [Slides] Daniel Dadush, Aleksandar Nikolov, Kunal Talwar, Nicole Tomczak-Jaegermann, Balancing Vectors in Any Norm, FOCS 2018.
[Local copy] [Quanta Magazine] Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten, Data-Dependent Hashing via Nonlinear Spectral Gaps, STOC 2018.
[arXiv] [Mathematika] Aleksandar Nikolov, Tighter Bounds for the Discrepancy of Boxes and Polytopes, Mathematika 63(3), 1091-1113, 2017.
[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] [Slides] 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).
[Rutgers copy][Local copy] New Computational Aspects of Discrepancy Theory, PhD Dissertation, Rutgers University, 2014.
[IMRN] [arXiv] Jiri Matousek, Aleksandar Nikolov, Kunal Talwar, Factorization Norms and Hereditary Discrepancy, IMRN (3), 751-780, 2020. This is a merged and simplified version of the following two papers:
- [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.
[Proc. AMS] [arXiv] [Blog] Aleksandar Nikolov, Kunal Talwar, On the Heredtary Discrepancy of Homogeneous Arithmetic Progressions. Proceedings of the American Mathematical Society, 143 (2015).
[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] [Slides] S. Mutkukrishnan, Aleksandar Nikolov, Optimal Private Halfspace Counting via Discrepancy, 2012 ACM Symposium on Theory of Computing (STOC 2012).
[arXiv] Alantha Newman, Aleksandar Nikolov, A Counterexample to Beck's Conjecture on the Discrepancy of Three Permutations, arXiv:1104.2922. Awarded $100 by Joel Spencer, as reported by Gil Kalai.
[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] [Slides] Moses Charikar, Alantha Newman, Aleksandar Nikolov, Tight Hardness Results for Minimizing Discrepancy, 2011 SIAM Symposium on Discrete Algorithms (SODA 11).
[PDF] Aleksandar Nikolov, Shenzhi Li, William M. Pottenger, Privacy-Enhancing Distributed Higher-Order ARM. Workshop on Link Analysis, Counterterrorism, and Security, SDM 2009.
Some Links
- The slides of a introductory talk to discrepancy theory I gave at the U of T Undergraduate Theory Seminar.
- Here is a PDF version of a blog post I wrote for Sebastien Bubeck's blog about beating the Monte Carlo method for numerical integration using low-discrepancy sequences.
- Here are my scribe notes from a lecture by Moses Charikar on efficiently finding small discrepancy colorings of general hypergraphs. Joel Spencer wrote an exposition himself. Nikhil Bansal's original paper is a great read, too.
- To learn more about discrepancy and its applications in computer science, check out Chazelle's book. There is also a brief summary in the introduction of my thesis.
- For an introduction to differential privacy, look at Cynthia Dwork and Aaron Roth's monograph.
- My survey talk on Differential Privacy in the Streaming World, from the Simons Institute workshop on Differential Privacy and Big Data, part of the Big Data Program.
- I scribed half the proof of the PCP theorem as presented by Prahladh Harsha at a DIMACS workshop on Limits of Approximation Algorithms. Here are the notes for the whole workshop.