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] 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] 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] 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] Aleksandar Nikolov, Shenzhi Li, William M. Pottenger, Privacy-Enhancing Distributed Higher-Order ARM. Workshop on Link Analysis, Counterterrorism, and Security, SDM 2009.
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
- 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
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.