סמינר: 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
Add to:
Lecturer: Tomer Berg
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.

 

כל הסמינרים
דילוג לתוכן