We investigate tolerant testing and distance estimation problems in distribution testing when the amount of memory is limited. In particular, our aim is to provide a good estimate of the distance measure (in total variation distance) using constant memory words. Though the problems are well understood in the standard access model with an \(\Omega (\frac{n}{\log {n}})\) lower bound, it has not been explored under memory constraints. We propose algorithms that require \(O(\frac{n}{\epsilon ^{7}})\) queries for estimating distance to a known distribution and \(O(\frac{n}{\epsilon ^{6}})\) queries (where \(\epsilon \in (0,1)\) is an error parameter) for estimating distance to uniformity that use only O(1) memory words. Our algorithms match the \(\Omega (\frac{n}{\epsilon ^4})\) lower bound established by [19] in terms of the dependence on n. Additionally, we present an \((\epsilon ,c\epsilon )\) tolerant closeness tester in terms of \(\ell _2\) distance for all \(c\ge 3\) , which requires \(O(\frac{n^3}{m\epsilon ^2})\) samples and O(m) bits of memory for \(\log {n}/\epsilon ^4 \le m\le n/\epsilon ^2\) . Furthermore, we outline an \(O(\frac{n^2\epsilon _1^2}{m\epsilon _2^4})\) trade-off for \((\epsilon _1,\epsilon _2)\) tolerant closeness testing problem \((0<\epsilon _1<\epsilon _2<1)\) using \(\ell _1\) distance, where \(\log {n} \le m\le n\log {n}\) is the available memory in bits.

Tolerant Testing and Distance Estimation for Distributions Under Memory Constraints

会议论文
发表日期：

2025年

查看全文

Sampriti Roy,
Yadu Vasudev

摘要

We investigate tolerant testing and distance estimation problems in distribution testing when the amount of memory is limited. In particular, our aim is to provide a good estimate of the distance measure (in total variation distance) using constant memory words. Though the problems are well understood in the standard access model with an \(\Omega (\frac{n}{\log {n}})\) lower bound, it has not been explored under memory constraints. We propose algorithms that require \(O(\frac{n}{\epsilon ^{7}})\) queries for estimating distance to a known distribution and \(O(\frac{n}{\epsilon ^{6}})\) queries (where \(\epsilon \in (0,1)\) is an error parameter) for estimating distance to uniformity that use only O(1) memory words. Our algorithms match the \(\Omega (\frac{n}{\epsilon ^4})\) lower bound established by [19] in terms of the dependence on n. Additionally, we present an \((\epsilon ,c\epsilon )\) tolerant closeness tester in terms of \(\ell _2\) distance for all \(c\ge 3\) , which requires \(O(\frac{n^3}{m\epsilon ^2})\) samples and O(m) bits of memory for \(\log {n}/\epsilon ^4 \le m\le n/\epsilon ^2\) . Furthermore, we outline an \(O(\frac{n^2\epsilon _1^2}{m\epsilon _2^4})\) trade-off for \((\epsilon _1,\epsilon _2)\) tolerant closeness testing problem \((0<\epsilon _1<\epsilon _2<1)\) using \(\ell _1\) distance, where \(\log {n} \le m\le n\log {n}\) is the available memory in bits.