Aleksandar Nikolov

According to our database, Aleksandar Nikolov authored at least 55 papers between 2010 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

On the Gap Between Hereditary Discrepancy and the Determinant Lower Bound.

Lily Li, Aleksandar Nikolov

SIAM J. Discret. Math., 2024

General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation.

Aleksandar Nikolov, Haohua Tang

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Gaussian Noise is Nearly Instance Optimal for Private Unbiased Mean Estimation.

Aleksandar Nikolov, Haohua Tang

CoRR, 2023

Private Query Release via the Johnson-Lindenstrauss Transform.

Aleksandar Nikolov

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Partitioning Friends Fairly.

Lily Li, Evi Micha, Aleksandar Nikolov, Nisarg Shah

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022

Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems.

Sepehr Abbasi Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh

ACM Trans. Algorithms, 2022

Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design.

Aleksandar Nikolov, Mohit Singh, Uthaipon Tao Tantipongpipat

Math. Oper. Res., 2022

Learning versus Refutation in Noninteractive Local Differential Privacy.

Alexander Edmonds, Aleksandar Nikolov, Toniann Pitassi

CoRR, 2022

On Learning and Refutation in Noninteractive Local Differential Privacy.

Alexander Edmonds, Aleksandar Nikolov, Toniann Pitassi

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021

Approximate Nearest Neighbors Beyond Space Partitions.

Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Near Neighbor Search via Efficient Average Distortion Embeddings.

Deepanshu Kush, Aleksandar Nikolov, Haohua Tang

Proceedings of the 37th International Symposium on Computational Geometry, 2021

2020

Program for TPDP 2018.

Aleksandar Nikolov, Lars Vilhuber

J. Priv. Confidentiality, 2020

Editorial for Special Issue on the Theory and Practice of Differential Privacy 2018.

Aleksandar Nikolov, Lars Vilhuber

J. Priv. Confidentiality, 2020

Preconditioning for the Geometric Transportation Problem.

Andrey Boris Khesin, Aleksandar Nikolov, Dmitry Paramonov

J. Comput. Geom., 2020

The power of factorization mechanisms in local and central differential privacy.

Alexander Edmonds, Aleksandar Nikolov, Jonathan R. Ullman

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Private Query Release Assisted by Public Data.

Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan R. Ullman, Zhiwei Steven Wu

Proceedings of the 37th International Conference on Machine Learning, 2020

Maximizing Determinants under Matroid Constraints.

Vivek Madan, Aleksandar Nikolov, Mohit Singh, Uthaipon Tantipongpipat

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

On the Computational Complexity of Linear Discrepancy.

Lily Li, Aleksandar Nikolov

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Locally Private Hypothesis Selection.

Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, Huanyu Zhang

Proceedings of the Conference on Learning Theory, 2020

2019

Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem.

Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandar Nikolov

Theory Comput., 2019

Towards Instance-Optimal Private Query Release.

Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

On Mean Estimation for General Norms with Statistical Queries.

Jerry Li, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the Conference on Learning Theory, 2019

2018

Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue.

Arnab Bhattacharyya, Fabrizio Grandoni, Aleksandar Nikolov, Barna Saha, Saket Saurabh, Aravindan Vijayaraghavan, Qin Zhang

ACM Trans. Algorithms, 2018

Data-dependent hashing via nonlinear spectral gaps.

Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Balancing Vectors in Any Norm.

Daniel Dadush, Aleksandar Nikolov, Kunal Talwar, Nicole Tomczak-Jaegermann

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Hölder Homeomorphisms and Approximate Nearest Neighbors.

Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Tighter Bounds for the Discrepancy of Boxes and Polytopes.

Aleksandar Nikolov

CoRR, 2017

Tusnády's problem, the transference principle, and non-uniform QMC sampling.

Christoph Aistleitner, Dmitriy Bilyk, Aleksandar Nikolov

CoRR, 2017

Approximate near neighbors for general symmetric norms.

Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Lower Bounds for Differential Privacy from Gaussian Width.

Assimakis Kattis, Aleksandar Nikolov

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016

Geometric Approaches to Answering Queries.

Aleksandar Nikolov

Encyclopedia of Algorithms, 2016

The Geometry of Differential Privacy: The Small Database and Approximate Cases.

Aleksandar Nikolov, Kunal Talwar, Li Zhang

SIAM J. Comput., 2016

Approximate Near Neighbors for General Symmetric Norms.

Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

CoRR, 2016

Maximizing determinants under partition constraints.

Aleksandar Nikolov, Mohit Singh

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations.

Cynthia Dwork, Aleksandar Nikolov, Kunal Talwar

Discret. Comput. Geom., 2015

Randomized Rounding for the Largest Simplex Problem.

Aleksandar Nikolov

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Approximating Hereditary Discrepancy via Small Width Ellipsoids.

Aleksandar Nikolov, Kunal Talwar

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

An Improved Private Mechanism for Small Databases.

Aleksandar Nikolov

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Combinatorial Discrepancy for Boxes via the gamma_2 Norm.

Jirí Matousek, Aleksandar Nikolov

Proceedings of the 31st International Symposium on Computational Geometry, 2015

2014

Randomized Rounding for the Largest $j$-Simplex Problem.

Aleksandar Nikolov

CoRR, 2014

Factorization Norms and Hereditary Discrepancy.

Jirí Matousek, Aleksandar Nikolov, Kunal Talwar

CoRR, 2014

Parallel algorithms for geometric graph problems.

Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev

Proceedings of the Symposium on Theory of Computing, 2014

Using Convex Relaxations for Efficiently and Privately Releasing Marginals.

Cynthia Dwork, Aleksandar Nikolov, Kunal Talwar

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013

The Komlos Conjecture Holds for Vector Colorings

Aleksandar Nikolov

CoRR, 2013

The geometry of differential privacy: the sparse and approximate cases.

Aleksandar Nikolov, Kunal Talwar, Li Zhang

Proceedings of the Symposium on Theory of Computing Conference, 2013

Private decayed predicate sums on streams.

Jean Bolot, Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov, Nina Taft

Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

Nearly Optimal Private Convolution.

Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov

Proceedings of the Algorithms - ESA 2013, 2013

2012

Optimal private halfspace counting via discrepancy.

S. Muthukrishnan, Aleksandar Nikolov

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Beck's Three Permutations Conjecture: A Counterexample and Some Consequences.

Alantha Newman, Ofer Neiman, Aleksandar Nikolov

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Private Decayed Sum Estimation under Continual Observation

Jean Bolot, Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov, Nina Taft

CoRR, 2011

A counterexample to Beck's conjecture on the discrepancy of three permutations

Alantha Newman, Aleksandar Nikolov

CoRR, 2011

Tight Hardness Results for Minimizing Discrepancy.

Moses Charikar, Alantha Newman, Aleksandar Nikolov

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Pan-private algorithms via statistics on sketches.

Darakhshan J. Mir, S. Muthukrishnan, Aleksandar Nikolov, Rebecca N. Wright

Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011

2010

Pan-private Algorithms: When Memory Does Not Help

Darakhshan J. Mir, S. Muthukrishnan, Aleksandar Nikolov, Rebecca N. Wright

CoRR, 2010

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

Prahladh Harsha, Moses Charikar, Matthew Andrews, Sanjeev Arora, Subhash Khot, Dana Moshkovitz, Lisa Zhang, Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan, Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, David Pritchard, Gwen Spencer

CoRR, 2010