Aleksandar Nikolov

Publication Activity (10 Years)

Years Active: 2010-2024
Publications (10 Years): 52

Top Topics

Approximation Algorithms

Differential Privacy

Top Venues

Publications

Aleksandar Nikolov, Haohua Tang
General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation. ITCS (2024)
Lily Li, Aleksandar Nikolov
On the Gap Between Hereditary Discrepancy and the Determinant Lower Bound. SIAM J. Discret. Math. 38 (2) (2024)
Lily Li, Aleksandar Nikolov
On the Gap between Hereditary Discrepancy and the Determinant Lower Bound. CoRR (2023)
Aleksandar Nikolov
Private Query Release via the Johnson-Lindenstrauss Transform. SODA (2023)
Lily Li, Evi Micha, Aleksandar Nikolov, Nisarg Shah
Partitioning Friends Fairly. AAAI (2023)
Aleksandar Nikolov, Haohua Tang
Gaussian Noise is Nearly Instance Optimal for Private Unbiased Mean Estimation. CoRR (2023)
Alexander Edmonds, Aleksandar Nikolov, Toniann Pitassi
On Learning and Refutation in Noninteractive Local Differential Privacy. NeurIPS (2022)
Alexander Edmonds, Aleksandar Nikolov, Toniann Pitassi
Learning versus Refutation in Noninteractive Local Differential Privacy. CoRR (2022)
Sepehr Abbasi Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems. ACM Trans. Algorithms 18 (4) (2022)
Aleksandar Nikolov
Private Query Release via the Johnson-Lindenstrauss Transform. CoRR (2022)
Aleksandar Nikolov, Mohit Singh, Uthaipon Tao Tantipongpipat
Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design. Math. Oper. Res. 47 (2) (2022)
Deepanshu Kush, Aleksandar Nikolov, Haohua Tang
Near Neighbor Search via Efficient Average Distortion Embeddings. SoCG (2021)
Deepanshu Kush, Aleksandar Nikolov, Haohua Tang
Near Neighbor Search via Efficient Average Distortion Embeddings. CoRR (2021)
Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Approximate Nearest Neighbors Beyond Space Partitions. SODA (2021)
Lily Li, Aleksandar Nikolov
On the Computational Complexity of Linear Discrepancy. ESA (2020)
Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan R. Ullman, Zhiwei Steven Wu
Private Query Release Assisted by Public Data. ICML (2020)
Aleksandar Nikolov, Lars Vilhuber
Editorial for Special Issue on the Theory and Practice of Differential Privacy 2018. J. Priv. Confidentiality 10 (1) (2020)
Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, Huanyu Zhang
Locally Private Hypothesis Selection. CoRR (2020)
Vivek Madan, Aleksandar Nikolov, Mohit Singh, Uthaipon Tantipongpipat
Maximizing Determinants under Matroid Constraints. CoRR (2020)
Andrey Boris Khesin, Aleksandar Nikolov, Dmitry Paramonov
Preconditioning for the Geometric Transportation Problem. J. Comput. Geom. 11 (2) (2020)
Lily Li, Aleksandar Nikolov
On the Computational Complexity of Linear Discrepancy. CoRR (2020)
Aleksandar Nikolov, Lars Vilhuber
Program for TPDP 2018. J. Priv. Confidentiality 10 (1) (2020)
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)
Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan R. Ullman, Zhiwei Steven Wu
Private Query Release Assisted by Public Data. CoRR (2020)
Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, Huanyu Zhang
Locally Private Hypothesis Selection. COLT (2020)
Vivek Madan, Aleksandar Nikolov, Mohit Singh, Uthaipon Tantipongpipat
Maximizing Determinants under Matroid Constraints. FOCS (2020)
Alexander Edmonds, Aleksandar Nikolov, Jonathan R. Ullman
The power of factorization mechanisms in local and central differential privacy. STOC (2020)
Andrey Boris Khesin, Aleksandar Nikolov, Dmitry Paramonov
Preconditioning for the Geometric Transportation Problem. CoRR (2019)
Andrey Boris Khesin, Aleksandar Nikolov, Dmitry Paramonov
Preconditioning for the Geometric Transportation Problem. SoCG (2019)
Jerry Li, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
On Mean Estimation for General Norms with Statistical Queries. COLT (2019)
Jerry Li, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
On Mean Estimation for General Norms with Statistical Queries. CoRR (2019)
Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke
Towards Instance-Optimal Private Query Release. SODA (2019)
Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandar Nikolov
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem. Theory Comput. 15 (2019)
Aleksandar Nikolov, Mohit Singh, Uthaipon Tao Tantipongpipat
Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design. SODA (2019)
Alexander Edmonds, Aleksandar Nikolov, Jonathan R. Ullman
The Power of Factorization Mechanisms in Local and Central Differential Privacy. CoRR (2019)
Aleksandar Nikolov, Mohit Singh, Uthaipon Tao Tantipongpipat
Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design. CoRR (2018)
Arnab Bhattacharyya, Fabrizio Grandoni, Aleksandar Nikolov, Barna Saha, Saket Saurabh, Aravindan Vijayaraghavan, Qin Zhang
Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue. ACM Trans. Algorithms 14 (3) (2018)
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Data-dependent hashing via nonlinear spectral gaps. STOC (2018)
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Hölder Homeomorphisms and Approximate Nearest Neighbors. FOCS (2018)
Sepehr Abbasi Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems. CoRR (2018)
Daniel Dadush, Aleksandar Nikolov, Kunal Talwar, Nicole Tomczak-Jaegermann
Balancing Vectors in Any Norm. FOCS (2018)
Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke
Towards Instance-Optimal Private Query Release. CoRR (2018)
Aleksandar Nikolov
Tighter Bounds for the Discrepancy of Boxes and Polytopes. CoRR (2017)
Assimakis Kattis, Aleksandar Nikolov
Lower Bounds for Differential Privacy from Gaussian Width. SoCG (2017)
Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Approximate near neighbors for general symmetric norms. STOC (2017)
Christoph Aistleitner, Dmitriy Bilyk, Aleksandar Nikolov
Tusnády's problem, the transference principle, and non-uniform QMC sampling. CoRR (2017)
Aleksandar Nikolov, Kunal Talwar, Li Zhang
The Geometry of Differential Privacy: The Small Database and Approximate Cases. SIAM J. Comput. 45 (2) (2016)
Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandar Nikolov
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem. CoRR (2016)
Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandar Nikolov
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem. APPROX-RANDOM (2016)
Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Approximate Near Neighbors for General Symmetric Norms. CoRR (2016)
Aleksandar Nikolov, Mohit Singh
Maximizing determinants under partition constraints. STOC (2016)
Assimakis Kattis, Aleksandar Nikolov
Lower Bounds for Differential Privacy from Gaussian Width. CoRR (2016)
Jirí Matousek, Aleksandar Nikolov
Combinatorial Discrepancy for Boxes via the gamma_2 Norm. SoCG (2015)
Aleksandar Nikolov
Randomized Rounding for the Largest Simplex Problem. STOC (2015)
Aleksandar Nikolov
An Improved Private Mechanism for Small Databases. ICALP (1) (2015)
Cynthia Dwork, Aleksandar Nikolov, Kunal Talwar
Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations. Discret. Comput. Geom. 53 (3) (2015)
Aleksandar Nikolov, Kunal Talwar
Approximating Hereditary Discrepancy via Small Width Ellipsoids. SODA (2015)
Aleksandar Nikolov
An Improved Private Mechanism for Small Databases. CoRR (2015)
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev
Parallel Algorithms for Geometric Graph Problems. CoRR (2014)
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev
Parallel algorithms for geometric graph problems. STOC (2014)
Aleksandar Nikolov
Randomized Rounding for the Largest $j$-Simplex Problem. CoRR (2014)
Jirí Matousek, Aleksandar Nikolov, Kunal Talwar
Factorization Norms and Hereditary Discrepancy. CoRR (2014)
Cynthia Dwork, Aleksandar Nikolov, Kunal Talwar
Using Convex Relaxations for Efficiently and Privately Releasing Marginals. SoCG (2014)
Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov
Nearly Optimal Private Convolution. ESA (2013)
Cynthia Dwork, Aleksandar Nikolov, Kunal Talwar
Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations. CoRR (2013)
Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov
Nearly Optimal Private Convolution CoRR (2013)
Aleksandar Nikolov
The Komlos Conjecture Holds for Vector Colorings CoRR (2013)
Jean Bolot, Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov, Nina Taft
Private decayed predicate sums on streams. ICDT (2013)
Aleksandar Nikolov, Kunal Talwar
Approximating Hereditary Discrepancy via Small Width Ellipsoids. CoRR (2013)
Aleksandar Nikolov, Kunal Talwar, Li Zhang
The geometry of differential privacy: the sparse and approximate cases. STOC (2013)
S. Muthukrishnan, Aleksandar Nikolov
Optimal Private Halfspace Counting via Discrepancy CoRR (2012)
Alantha Newman, Ofer Neiman, Aleksandar Nikolov
Beck's Three Permutations Conjecture: A Counterexample and Some Consequences. FOCS (2012)
S. Muthukrishnan, Aleksandar Nikolov
Optimal private halfspace counting via discrepancy. STOC (2012)
Aleksandar Nikolov, Kunal Talwar, Li Zhang
The Geometry of Differential Privacy: the Sparse and Approximate Cases CoRR (2012)
Darakhshan J. Mir, S. Muthukrishnan, Aleksandar Nikolov, Rebecca N. Wright
Pan-private algorithms via statistics on sketches. PODS (2011)
Moses Charikar, Alantha Newman, Aleksandar Nikolov
Tight Hardness Results for Minimizing Discrepancy. SODA (2011)
Jean Bolot, Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov, Nina Taft
Private Decayed Sum Estimation under Continual Observation CoRR (2011)
Alantha Newman, Aleksandar Nikolov
A counterexample to Beck's conjecture on the discrepancy of three permutations CoRR (2011)
Darakhshan J. Mir, S. Muthukrishnan, Aleksandar Nikolov, Rebecca N. Wright
Pan-private Algorithms: When Memory Does Not Help CoRR (2010)
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
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes) CoRR (2010)