Aleksandar Nikolov

Generating author description...

All published works

Action	Title	Year	Authors
+ PDF Chat	On the Gap Between Hereditary Discrepancy and the Determinant Lower Bound	2024	Lily Li Aleksandar Nikolov
+ PDF Chat	Private Query Release via the Johnson-Lindenstrauss Transform	2023	Aleksandar Nikolov
+	General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation	2023	Aleksandar Nikolov Haohua Tang
+	On the Gap between Hereditary Discrepancy and the Determinant Lower Bound	2023	Lily Li Aleksandar Nikolov
+ PDF Chat	Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design	2022	Aleksandar Nikolov Mohit Singh Uthaipon Tantipongpipat
+ PDF Chat	Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems	2022	Sepehr Abbasi-Zadeh Nikhil Bansal Guru Guruganesh Aleksandar Nikolov Roy Schwartz Mohit Singh
+	Private Query Release via the Johnson-Lindenstrauss Transform	2022	Aleksandar Nikolov
+	Learning versus Refutation in Noninteractive Local Differential Privacy	2022	Alexander Edmonds Aleksandar Nikolov Toniann Pitassi
+ PDF Chat	Near Neighbor Search via Efficient Average Distortion Embeddings	2021	Deepanshu Kush Aleksandar Nikolov Haohua Tang
+	Near Neighbor Search via Efficient Average Distortion Embeddings	2021	Deepanshu Kush Aleksandar Nikolov Haohua Tang
+ PDF Chat	Maximizing Determinants under Matroid Constraints	2020	Vivek Madan Aleksandar Nikolov Mohit Singh Uthaipon Tantipongpipat
+ PDF Chat	The power of factorization mechanisms in local and central differential privacy	2020	Alexander Edmonds Aleksandar Nikolov Jonathan Ullman
+	Private Query Release Assisted by Public Data	2020	Raef Bassily Albert Cheu Shay Moran Aleksandar Nikolov Jonathan Ullman Zhiwei Steven Wu
+	Maximizing Determinants under Matroid Constraints	2020	Vivek Madan Aleksandar Nikolov Mohit Singh Uthaipon Tantipongpipat
+	8. Some of Jiří Matoušek’s contributions to combinatorial discrepancy theory	2020	Aleksandar Nikolov
+	Locally Private Hypothesis Selection	2020	Sivakanth Gopi Gautam Kamath Janardhan Kulkarni Aleksandar Nikolov Zhiwei Steven Wu Huanyu Zhang
+	On the Computational Complexity of Linear Discrepancy	2020	Lily Li Aleksandar Nikolov
+	On the Computational Complexity of Linear Discrepancy	2020	Lily Li Aleksandar Nikolov
+	Private Query Release Assisted by Public Data	2020	Raef Bassily Albert Cheu Shay Moran Aleksandar Nikolov Jonathan Ullman Zhiwei Steven Wu
+	Maximizing Determinants under Matroid Constraints	2020	Vivek Madan Aleksandar Nikolov Mohit Singh Uthaipon Tantipongpipat
+ PDF Chat	Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems	2019	Sepehr Abbasi-Zadeh Nikhil Bansal Guru Guruganesh Aleksandar Nikolov Roy Schwartz Mohit Singh
+	The Power of Factorization Mechanisms in Local and Central Differential Privacy	2019	Alexander Edmonds Aleksandar Nikolov Jonathan Ullman
+ PDF Chat	None	2019	Daniel Dadush Shashwat Garg Shachar Lovett Aleksandar Nikolov
+ PDF Chat	Towards Instance-Optimal Private Query Release	2019	Jarosław Błasiok Mark Bun Aleksandar Nikolov Thomas Steinke
+	On Mean Estimation for General Norms with Statistical Queries	2019	Jerry Li Aleksandar Nikolov Ilya Razenshteyn Erik Waingarten
+	Preconditioning for the Geometric Transportation Problem	2019	Andrey Boris Khesin Aleksandar Nikolov Dmitry Paramonov
+	Preconditioning for the Geometric Transportation Problem	2019	Andrey Boris Khesin Aleksandar Nikolov Dmitry Paramonov
+	The Power of Factorization Mechanisms in Local and Central Differential Privacy	2019	Alexander Edmonds Aleksandar Nikolov Jonathan Ullman
+	Balancing Vectors in Any Norm	2018	Daniel Dadush Aleksandar Nikolov Kunal Talwar Nicole Tomczak-Jaegermann
+ PDF Chat	Factorization Norms and Hereditary Discrepancy	2018	Jiřı́ Matoušek Aleksandar Nikolov Kunal Talwar
+ PDF Chat	Tusnády’s Problem, the Transference Principle, and Non-uniform QMC Sampling	2018	Christoph Aistleitner Dmitriy Bilyk Aleksandar Nikolov
+	Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems	2018	Sepehr Abbasi-Zadeh Nikhil Bansal Guru Guruganesh Aleksandar Nikolov Roy Schwartz Mohit Singh
+	Towards Instance-Optimal Private Query Release	2018	Jarosław Błasiok Mark Bun Aleksandar Nikolov Thomas Steinke
+	Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design	2018	Aleksandar Nikolov Mohit Singh Uthaipon Tantipongpipat
+	Approximate near neighbors for general symmetric norms	2017	Alexandr Andoni Huy L. Nguyễn Aleksandar Nikolov Ilya Razenshteyn Erik Waingarten
+	Tusn\'ady's problem, the transference principle, and non-uniform QMC sampling	2017	Christoph Aistleitner Dmitriy Bilyk Aleksandar Nikolov
+	Tighter Bounds for the Discrepancy of Boxes and Polytopes	2017	Aleksandar Nikolov
+ PDF Chat	TIGHTER BOUNDS FOR THE DISCREPANCY OF BOXES AND POLYTOPES	2017	Aleksandar Nikolov
+	Tusnády's problem, the transference principle, and non-uniform QMC sampling	2017	Christoph Aistleitner Dmitriy Bilyk Aleksandar Nikolov
+	Tighter Bounds for the Discrepancy of Boxes and Polytopes	2017	Aleksandar Nikolov
+	Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem	2016	Daniel Dadush Shashwat Garg Shachar Lovett Aleksandar Nikolov
+	Maximizing determinants under partition constraints	2016	Aleksandar Nikolov Mohit Singh
+	Lower Bounds for Differential Privacy from Gaussian Width	2016	Assimakis Kattis Aleksandar Nikolov
+	Approximate Near Neighbors for General Symmetric Norms	2016	Alexandr Andoni Huy L. Nguyễn Aleksandar Nikolov Ilya Razenshteyn Erik Waingarten
+	Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem	2016	Daniel Dadush Shashwat Garg Shachar Lovett Aleksandar Nikolov
+ PDF Chat	Randomized Rounding for the Largest Simplex Problem	2015	Aleksandar Nikolov
+	An Improved Private Mechanism for Small Databases	2015	Aleksandar Nikolov
+ PDF Chat	Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations	2015	Cynthia Dwork Aleksandar Nikolov Kunal Talwar
+ PDF Chat	On the hereditary discrepancy of homogeneous arithmetic progressions	2015	Aleksandar Nikolov Kunal Talwar
+	Approximating hereditary discrepancy via small width ellipsoids	2015	Aleksandar Nikolov Kunal Talwar
+ PDF Chat	An Improved Private Mechanism for Small Databases	2015	Aleksandar Nikolov
+	Combinatorial Discrepancy for Boxes via the gamma_2 Norm.	2015	Jiřı́ Matoušek Aleksandar Nikolov
+	An Improved Private Mechanism for Small Databases	2015	Aleksandar Nikolov
+	Approximating Hereditary Discrepancy via Small Width Ellipsoids	2014	Aleksandar Nikolov Kunal Talwar
+	Randomized Rounding for the Largest Simplex Problem	2014	Aleksandar Nikolov
+	Factorization Norms and Hereditary Discrepancy	2014	Jiřı́ Matoušek Aleksandar Nikolov Kunal Talwar
+	Combinatorial Discrepancy for Boxes via the Ellipsoid-Infinity Norm	2014	Jiřı́ Matoušek Aleksandar Nikolov
+ PDF Chat	Parallel algorithms for geometric graph problems	2014	Alexandr Andoni Aleksandar Nikolov Krzysztof Onak Grigory Yaroslavtsev
+	NEW COMPUTATIONAL ASPECTS OF DISCREPANCY THEORY	2014	Aleksandar Nikolov S. Muthukrishnan
+	Randomized Rounding for the Largest Simplex Problem	2014	Aleksandar Nikolov
+	Parallel Algorithms for Geometric Graph Problems	2014	Alexandr Andoni Aleksandar Nikolov Krzysztof Onak Grigory Yaroslavtsev
+	Factorization Norms and Hereditary Discrepancy	2014	Jiřı́ Matoušek Aleksandar Nikolov Kunal Talwar
+	On The Hereditary Discrepancy of Homogeneous Arithmetic Progressions	2013	Aleksandar Nikolov Kunal Talwar
+	Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations	2013	Cynthia Dwork Aleksandar Nikolov Kunal Talwar
+ PDF Chat	The geometry of differential privacy	2013	Aleksandar Nikolov Kunal Talwar Li Zhang
+ PDF Chat	Private decayed predicate sums on streams	2013	Jean Bolot Nadia Fawaz S. Muthukrishnan Aleksandar Nikolov Nina Taft
+	Nearly Optimal Private Convolution	2013	Nadia Fawaz S. Muthukrishnan Aleksandar Nikolov
+	The Komlos Conjecture Holds for Vector Colorings	2013	Aleksandar Nikolov
+ PDF Chat	Nearly Optimal Private Convolution	2013	Nadia Fawaz S. Muthukrishnan Aleksandar Nikolov
+	On The Hereditary Discrepancy of Homogeneous Arithmetic Progressions	2013	Aleksandar Nikolov Kunal Talwar
+	Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations	2013	Cynthia Dwork Aleksandar Nikolov Kunal Talwar
+	On The Hereditary Discrepancy of Homogeneous Arithmetic Progressions	2013	Aleksandar Nikolov Kunal Talwar
+	Nearly Optimal Private Convolution	2013	Nadia Fawaz S. Muthukrishnan Aleksandar Nikolov
+	Approximating Hereditary Discrepancy via Small Width Ellipsoids	2013	Aleksandar Nikolov Kunal Talwar
+ PDF Chat	The Geometry of Differential Privacy: the Sparse and Approximate Cases	2012	Aleksandar Nikolov Kunal Talwar Li Zhang
+ PDF Chat	Beck's Three Permutations Conjecture: A Counterexample and Some Consequences	2012	Alantha Newman Ofer Neiman Aleksandar Nikolov
+ PDF Chat	Optimal private halfspace counting via discrepancy	2012	S. Muthukrishnan Aleksandar Nikolov
+	The Geometry of Differential Privacy: the Sparse and Approximate Cases	2012	Aleksandar Nikolov Kunal Talwar Li Zhang
+	Optimal Private Halfspace Counting via Discrepancy	2012	S. Muthukrishnan Aleksandar Nikolov
+	Tight Hardness Results for Minimizing Discrepancy	2011	Moses Charikar Alantha Newman Aleksandar Nikolov
+	A counterexample to Beck's conjecture on the discrepancy of three permutations	2011	Alantha Newman Aleksandar Nikolov
+	Pan-private Algorithms: When Memory Does Not Help	2010	Darakhshan Mir S. Muthukrishnan Aleksandar Nikolov Rebecca N. Wright
+	Pan-private Algorithms: When Memory Does Not Help	2010	Darakhshan Mir S. Muthukrishnan Aleksandar Nikolov Rebecca N. Wright
+	Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)	2010	Prahladh Harsha Moses Charikar Matthew Andrews Sanjeev Arora Subhash Khot Dana Moshkovitz Lisa Zhang Ashkan Aazami Dev Desai Igor Gorodezky
+	Fourier decomposition of Cepheid light curves.	1994	Aleksandar Nikolov

Common Coauthors

Coauthor	Papers Together
Kunal Talwar	17
Mohit Singh	6
Uthaipon Tantipongpipat	5
Jonathan Ullman	5
Jiřı́ Matoušek	5
Nadia Fawaz	4
Alexandr Andoni	4
Alantha Newman	4
Lily Li	4
Daniel Dadush	4
S. Muthukrishnan	4
Nikhil Bansal	3
Dmitriy Bilyk	3
S. Muthukrishnan	3
Christoph Aistleitner	3
Cynthia Dwork	3
Sepehr Abbasi-Zadeh	3
Erik Waingarten	3
Li Zhang	3
Zhiwei Steven Wu	3
Shachar Lovett	3
Mohit Singh	3
Shashwat Garg	3
Haohua Tang	3
Ilya Razenshteyn	3
Guru Guruganesh	3
Vivek Madan	3
Darakhshan Mir	3
Shay Moran	2
Albert Cheu	2
Thomas Steinke	2
Rebecca N. Wright	2
Roy Schwartz	2
Deepanshu Kush	2
Krzysztof Onak	2
Alexander Edmonds	2
Raef Bassily	2
Andrey Boris Khesin	2
Jarosław Błasiok	2
Mark Bun	2
Grigory Yaroslavtsev	2
Huy L. Nguyên	2
Moses Charikar	2
Dmitry Paramonov	2
S. Muthukrishnan	2
Jerry Li	1
Toniann Pitassi	1
Roy Schwartz	1
Alexander Edmonds	1
Ashkan Aazami	1

Commonly Cited References

Action	Title	Year	Authors	# of times referenced
+	Discrepancy of Set-systems and Matrices	1986	László Lovász J. Spencer K. Vesztergombi	22
+	Privately releasing conjunctions and the statistical query barrier	2011	Anupam Gupta Moritz Hardt Aaron Roth Jonathan Ullman	14
+	Balancing vectors and Gaussian measures ofn-dimensional convex bodies	1998	Wojciech Banaszczyk	12
+	Tight Hardness Results for Minimizing Discrepancy	2011	Moses Charikar Alantha Newman Aleksandar Nikolov	12
+	Invertibility of ‘large’ submatrices with applications to the geometry of Banach spaces and harmonic analysis	1987	Jean Bourgain Lior Tzafriri	12
+ PDF Chat	A learning theory approach to non-interactive database privacy	2008	Avrim Blum Katrina Ligett Aaron Roth	11
+	The Discrepancy Method	1998	Bernard Chazelle	10
+ PDF Chat	Interactive privacy via the median mechanism	2010	Aaron Roth Tim Roughgarden	10
+ PDF Chat	Constructive Algorithms for Discrepancy Minimization	2010	Nikhil Bansal	10
+ PDF Chat	On the geometry of differential privacy	2010	Moritz Hardt Kunal Talwar	9
+	John's decompositions: Selecting a large part	2001	Roman Vershynin	9
+	On irregularities of distribution	1954	K. F. Roth	9
+ PDF Chat	Optimal private halfspace counting via discrepancy	2012	S. Muthukrishnan Aleksandar Nikolov	9
+ PDF Chat	An elementary proof of the restricted invertibility theorem	2011	Daniel A. Spielman Nikhil Srivastava	8
+	Convex Optimization	2004	Stephen Boyd Lieven Vandenberghe	8
+ PDF Chat	Six standard deviations suffice	1985	Joel Spencer	7
+	The Convex Analysis of Unitarily Invariant Matrix Functions	1995	Adrian S. Lewis	7
+	Constructive Algorithms for Discrepancy Minimization	2010	Nikhil Bansal	7
+	Improving the discrepancy bound for sparse matrices: better approximations for sparse lattice approximation problems	1997	Aravind Srinivasan	7
+	On the Discrepancy for Boxes and Polytopes	1999	Jirří Matousšek	7
+	On Range Searching in the Group Model and Combinatorial Discrepancy	2014	Kasper Green Larsen	7
+	“Integer-making” theorems	1981	József Beck Tibor Fiala	7
+	EXTREMAL PROPERTIES OF ORTHOGONAL PARALLELEPIPEDS AND THEIR APPLICATIONS TO THE GEOMETRY OF BANACH SPACES	1989	E. D. Gluskin	6
+ PDF Chat	Optimizing linear counting queries under differential privacy	2010	Chao Li Michael Hay Vibhor Rastogi Gerome Miklau Andrew McGregor	6
+	On the Small Ball Inequality in all dimensions	2007	Dmitriy Bilyk Michael T. Lacey Armen Vagharshakyan	6
+	The discrepancy method: randomness and complexity	2002	Bernard Chazelle	6
+ PDF Chat	A Trace Bound for the Hereditary Discrepancy	2001	Bernard Chazelle Alexey Lvov	6
+ PDF Chat	Randomized Rounding for the Largest Simplex Problem	2015	Aleksandar Nikolov	6
+	The determinant bound for discrepancy is almost tight	2012	Jiřı́ Matoušek	6
+	Approximating hereditary discrepancy via small width ellipsoids	2015	Aleksandar Nikolov Kunal Talwar	6
+	The determinant bound for discrepancy is almost tight	2013	Jiřı́ Matoušek	6
+	On series of signed vectors and their rearrangements	2011	Wojciech Banaszczyk	6
+ PDF Chat	Differential privacy via wavelet transforms	2010	Xiaokui Xiao Guozhang Wang Johannes Gehrke	5
+ PDF Chat	Fingerprinting codes and the price of approximate differential privacy	2014	Mark Bun Jonathan Ullman Salil Vadhan	5
+	Geometric Discrepancy	1999	Jiřı́ Matoušek	5
+ PDF Chat	Constructive Discrepancy Minimization by Walking on the Edges	2012	Shachar Lovett Raghu Meka	5
+ PDF Chat	Faster Algorithms for Privately Releasing Marginals	2012	Justin Thaler Jonathan Ullman Salil Vadhan	5
+	On the discrepancy of 3 permutations	1990	Géza Bohus	5
+	Optimal Private Halfspace Counting via Discrepancy	2012	S. Muthukrishnan Aleksandar Nikolov	5
+	Approximating Hereditary Discrepancy via Small Width Ellipsoids	2014	Aleksandar Nikolov Kunal Talwar	5
+	Balanced two-colorings of finite sets in the square I	1981	József Beck	5
+ PDF Chat	The Discrepancy of Boxes in Higher Dimension	2001	Bernard Chazelle Alexey Lvov	5
+ PDF Chat	Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix	2011	Ali Çivril Malik Magdon‐Ismail	5
+ PDF Chat	Complexity measures of sign matrices	2007	Nati Linial Shahar Mendelson Gideon Schechtman Adi Shraibman	5
+ PDF Chat	The Gram-Schmidt walk: a cure for the Banaszczyk blues	2018	Nikhil Bansal Daniel Dadush Shashwat Garg Shachar Lovett	5
+ PDF Chat	Tight upper bounds for the discrepancy of half-spaces	1995	Jiřı́ Matoušek	4
+	The Komlos Conjecture Holds for Vector Colorings	2013	Aleksandar Nikolov	4
+	On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals	1960	John H. Halton	4
+	Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias	1965	Stanley L. Warner	4
+ PDF Chat	An elementary approach to lower bounds in geometric discrepancy	1995	Bernard Chazelle Jiřı́ Matoušek Micha Sharir	4