Publications
I am interested in combinatorial discrepancy (including pure math questions, applications to computer science, and computational questions about discrepancy), and private data analysis algorithms. I think about connections like privacy:combinatorial discrepancy, privacy:sublinear algorithms, privacy:geometry, discrepancy:geometry, discrepancy:approximation algorithms. I am also interested in sublinear algorithms for massive data, approximation algorithms and hardness of approximation. Below you can find some of my work in these areas:
[PDF] Aleksandar Nikolov, The Komlos Conjecture Holds for Vector Colorings.
[PDF] [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).
[PDF] Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov, Nearly Optimal Private Convolution.
[PDF] 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] [Blog] Aleksandar Nikolov, Kunal Talwar, On the Hereditary Discrepancy of Homogeneous Arithmetic Progressions.
[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)
[PDF] [Slides] S. Mutkukrishnan, Aleksandar Nikolov, Optimal Private Halfspace Counting via Discrepancy, 2012 ACM Symposium on Theory of Computing (STOC 2012).
[PDF] 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.
[PDF] 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
- 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.
- 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.
- For an introduction to differential privacy, look at
Cynthia Dwork's
surveys: from
2008
and from
2009. You can find more recent results in Aaron
Roth's 2011 lecture notes.
- Here are my slides on Blum, Ligett, and Roth's paper on a learning theory approach to sanitizing databases.
- Here you can find the course materials of S. Muthu Muthukrishnan's algorithmic game theory course. The course was co-taught by MohammedTaghi HajiAghayi, and Aaron Jaggard. You can find detailed lecture notes, links to papers, and slides, including my own slides on network formation games.
Ideas and questions
Some questions I have been thinking about:
- On the surface, there seems to be a similarity between
differential privacy and various sublinear models: data
stream analysis, compressed sensing, and property
testing. In all these areas we need to extract a global
structure without relying too much on individual data
items. In sublinear algorithms the restrictions are
computational. In differential privacy, the restrictions
come from the privacy requirement. Is there a real
connection there?
- Here we explore a connection between streaming algorithms based on linear sketches, and algorithms with private state (pan-private algorithms). For many problems we can convert a sketching algorithm to a pan-private algorithm.
- If a problem can be solved in small space, can it be solved pan-privately? What about the converse?
- Can we define privacy in a purely game-theoretic way? Ultimately users make a rational decision about trading privacy for utility.
- A complexity theory question: What is the
computational complexity of hereditary discrepancy? Is the
decision problem
in NP? Higher in
the polynomial hierarchy? What is the hardness of
approximating hereditary discrepancy? We know:
- Computing hereditary discrepancy exactly is in (a functional analogue of) the second level of the polynomial hierarchy.
- Set systems with hereditary discrepancy 1 can be recognized in polynomial time by the characterization of totally unimodular matrices due to Seymour.
- Distinguishing systems with hereditary discrepancy 2 from systems with discrepancy 3 is NP-hard by a reduction from Exact 3-Set Splitting
- In a paper with Talwar and Zhang we proved hereditary discrepancy can be approximated to within polylogarithmic factors.