Seminar: The Jacob Ziv Communication and Information Theory seminar
On The Memory Complexity of Uniformity Testing
Date:
April,04,2024
Start Time:
14:30 - 15:30
Location:
1061, Meyer Building
Zoom:
Zoom link
Add to:
Lecturer:
Tomer Berg
Research Areas:
| In the problem of uniformity testing with limited memory, we observe a sequence of independent identically distributed random variables drawn from a distribution p over [n], which is either uniform or is epsilon-far from uniform under the total variation distance, and our goal is to determine the correct hypothesis. At each time point we are allowed to update the state of a finite-memory machine with S states, where each state of the machine is assigned one of the hypotheses, and we are interested in obtaining an asymptotic probability of error at most delta<1/2 uniformly under both hypotheses.
We derive upper and lower bounds on the number of states S needed in order to achieve a constant error probability delta, as a function of n and epsilon. Our upper bound of O(n*log(n) /epsilon) does not rely on collision counting and is tighter than previously known bounds. Our lower bound of Omega (n+ 1/epsilon) settles an open question on whether uniformity testing can be done in o(n) states.
|
| Ph.D. student under the supervision of Prof. Ofer Shayevitz.
|