Faster Algorithms for Testing under Conditional Sampling  thumbnail
Pause
Mute
Subtitles not available
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

Faster Algorithms for Testing under Conditional Sampling

Published on Aug 20, 20151940 Views

There has been considerable recent interest in distribution-tests whose run-time and sample requirements are sublinear in the domain-size $k$. We study two of the most important tests under the condit

Related categories

Chapter list

Faster Algorithms for Testing under Conditional Sampling00:00
Outline00:09
Testing distributions00:41
Conditional sampling01:45
Results02:58
Intuition03:50