Publications
I am interested in private algorithms and connections like privacy: combinatorial discrepancy, privacy:sublinear algorithms, privacy:high dimensional geometry, privacy:truthful mechanisms, privacy:learning theory. I am also interested in discrepancy theory, sublinear algorithms for massive data, approximation algorithms and hardness of approximation. Below you can find some of my work in these areas:
[Manuscript Coming Soon] S. Mutkukrishnan, Aleksandar Nikolov, Optimal Private Halfspace Counting via Discrepancy, to appear in the 2012 ACM Symposium on Theory of Computing (STOC 2012).
[PDF] Jean Bolot, Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov, Nina Taft, Private Decayed Sum Estimation under Continual Observation, arXiv:1108.6123.
[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 current research in differential privacy, look at Cynthia Dwork's surveys: from 2008 and from 2009. Time for a new survey?
- You can find more links to papers on differential
privacy on
this page
of a Rutgers seminar taught by Rebecca Wright.
- 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 from AT&T and MIT, and Aaron Jaggard from DIMACS. 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:
- We have good sanitization mechanisms for databases with
independent
rows. How do we do the same for graphs:
- What is the right notion of utility for a sanitized graph? What functions on graphs are important?
- Do we need to impose a distribution on graphs, in the same way we assume database rows are drawn iid from a data universe? This possibly relates to work on modelling social networks.
- Can we reduce the problem (in some special case) to sanitizing databases while preserving utility for counting queries?
- 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 that can be exploited?
- 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. But we also show that there exists a problem that requires more error to be approximated pan-privately, than to be approximated in small space.
- If a problem can be solved in small space, can it be solved pan-privately? What about the converse?
- Can we introduce game theory into privacy research? Ultimately users make a rational decision about trading privacy for utility. Can differential privacy and mechanism design, i.e. economic theory, capture this process nicely?
- 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: systems with hereditary discrepancy 1 can be recognized in polynomial time. Distinguishing systems with hereditary discrepancy 2 from systems with discrepancy 3 is NP-hard.