Date & Time:
November 5, 2019 3:30 pm – 4:30 pm
Ryerson 251, 1100 E. 58th St., Chicago, IL,
11/05/2019 03:30 PM 11/05/2019 04:30 PM America/Chicago Aleksandar Nikolov (Toronto) – The Power of Factorization Mechanisms in Differential Privacy Department of Mathematics & Computer Science Combinatorics & Theory Seminar Ryerson 251, 1100 E. 58th St., Chicago, IL,

The Power of Factorization Mechanisms in Differential Privacy

A central goal in private data analysis is to estimate statistics about an unknown distribution from a dataset possibly containing sensitive information, so that the privacy of any individual represented in the dataset is preserved. We study this question in the model of non-interactive local differential privacy (LDP), in which every person in the dataset randomizes their own data in order to preserve its privacy, before sending it to a central server. We give a characterization of the minimum number of samples necessary to get an accurate estimates of a given set of statistical queries, as well as a characterization of the sample complexity of agnostic PAC learning in this model. The characterization is tight up polylogarithmic factors for any given set of statistical queries, and, respectively, any given concept class. The characterization is achieved by a simple and efficient instance-optimal (with respect to the queries/concept class) approximate factorization mechanism, i.e. a mechanism that answers the statistical queries by answering a different set of strategy queries, from which the answers to the original queries can be approximately reconstructed. 

Based on joint work with Alexander Edmonds and Jonathan Ullman

Aleksandar Nikolov

Assistant Professor, Department of Computer Science, University of Toronto

I am broadly interested in theory of computation and algorithm design, and I am a part of the Theory Group. My current research interests are in the connections between high dimensional geometry and computer science. In my work, I have applied geometric tools to the theory of private data analysis (differential privacy), discrepancy theory, and experimental design. I have also worked on computational questions in high dimensions, such as nearest neighbor search, and various geometric optimization problems. I also think about approximation algorithms, and sublinear and parallel algorithms for analyzing massive data. For more information, look in Research. If any of the above sounds intriguing, and you are a talented and motivated student interested in the theory of computing and the design of algorithms, I encourage you to apply to the University of Toronto.

Before coming to Toronto, between October 2014 and July 2015, I was a postdoc researcher in the Theory Group at Microsoft Research in Redmond. Before that, I completed my PhD in Rutgers University's Computer Science department, where I was advised by Muthu. During 2012-2014 I was supported by a Simons Graduate Fellowship.

Related News & Events


Nightshade: Data Poisoning to Fight Generative AI with Ben Zhao

Jan 23, 2024
UChicago CS News

Research Suggests That Privacy and Security Protection Fell To The Wayside During Remote Learning

A qualitative research study conducted by faculty and students at the University of Chicago and University of Maryland revealed key...
Oct 18, 2023
UChicago CS News

UChicago Researchers Win Internet Defense Prize and Distinguished Paper Awards at USENIX Security

Sep 05, 2023
UChicago CS News

Chicago Public Schools Student Chris Deng Pursues Internet Equity with University of Chicago Faculty

May 16, 2023
UChicago CS News

Computer Science Displays Catch Attention at MSI’s Annual Robot Block Party

Apr 07, 2023
UChicago CS News

UChicago / School of the Art Institute Class Uses Art to Highlight Data Privacy Dangers

Apr 03, 2023
Young students on computers
UChicago CS News

UChicago and NYU Research Team Finds Edtech Tools Could Pose Privacy Risks For Students

Feb 21, 2023
UChicago CS News

UChicago Scientists Develop New Tool to Protect Artists from AI Mimicry

Feb 13, 2023
In the News

Professors Rebecca Willett and Ben Zhao Discuss the Future of AI on Public Radio

Jan 26, 2023
UChicago CS News

Professor Heather Zheng Named ACM Fellow

Jan 18, 2023
UChicago CS News

Professor Fred Chong Named IEEE Fellow

Dec 09, 2022
UChicago CS News

The Computing Pipeline: A Foundation for Diversifying Computer Science

Nov 28, 2022
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube