PhD Seminar • Algorithms and Complexity — Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube ConditioningExport this event to calendar

Monday, June 1, 2020 — 1:30 PM EDT

Please note: This PhD seminar will be given online

Amit Levi, PhD candidate
David R. Cheriton School of Computer Science

Given a distribution p supported on {-1,1}^n, we want to test whether p is uniform or ϵ-far from uniform in total variation distance. The fact that p is a high dimensional distribution is inconsequential for the sample complexity, which is well-known to be Θ(2^{n/2} / ε^2). To benefit from the high dimensional structure, we study the subcube conditional sampling model, first considered in Bhattacharyya and Chakraborty (2018), and give a nearly optimal algorithm for testing uniformity on {-1,1}^n making Õ(√n/ ε^2) queries. The key ingredient is a natural notion of random restriction for distributions on {-1,1}^n, and an inequality describing the behaviour of the mean vector after a random restriction. 

To join this PhD seminar on Zoom, please go to https://zoom.us/j/99723663216

Location 
Online PhD seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
  1. 2020 (133)
    1. August (2)
    2. July (11)
    3. June (19)
    4. May (17)
    5. April (20)
    6. March (17)
    7. February (25)
    8. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (220)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)