Search Mailing List Archives
[theory-seminar] Theory Lunch 10/24 - Clément Canonne
Neha Gupta
nehgupta at stanford.edu
Wed Oct 23 10:10:35 PDT 2019
Hi everyone,
This Thursday at theory lunch, Clément will tell us about "Uniformity Testing for High-Dimensional Distributions" (title and abstract below). As usual, please join us from noon - 1pm in Gates 463A.
-----------------------------
Title: Uniformity Testing for High-Dimensional Distributions: Subcube
Conditioning, Random Restrictions, and Mean Testing.
Abstract: Given a distribution p on {-1,1}^d, we want to test
whether p is uniform. If p is assumed to be a product distribution,
this can be done with Theta(sqrt{d}) samples; without this assumption,
then things get exponentially worse and Theta(sqrt{2^d}) are necessary
and sufficient. Assume however we can condition on arbitrary bits: does
the problem become easier? If so, how much?
This is the "subcube conditional sampling model", first considered in
Bhattacharyya and Chakraborty (2018). We provide a nearly optimal
~O(sqrt{d})-algorithm for testing uniformity in this model. The key
component of our proof is a natural notion of random restriction for
distributions on {-1,1}^d, and a quantitative analysis of how such a
restriction affects the mean vector of the distribution. Along the way,
we provide a /very/ nearly upper bound on the (unconditional) sample
complexity of a natural problem, "mean testing."
Joint work with Xi Chen, Gautam Kamath, Amit Levi, and Erik Waingarten.
-------------------------------
Thanks,
Neha
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20191023/46175919/attachment-0003.html>
More information about the theory-seminar
mailing list