Aleksandar Nikolov

87 papers A* 30A 5Journal 49Unranked 2

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