Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 10/24 - Clément Canonne

Neha Gupta nehgupta at
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.



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list