Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Amit Levi, Gopinath Mishra, Sayantan Sen · 2024
Read Testing vs Estimation for Index-Invariant Properties in the Huge Object Model by Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Amit Levi, Gopinath Mishra, Sayantan Sen (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-02235.txt.
Introduction
Sourav Chakraborty and co-authors prove that a cheap test for a class of vast string traits buys a gap gauge for the same traits, in a paper from 2024. The traits live on strings so long that one full read is out of reach. Probes sip bits of a few strings, and cost counts probes, not time.
The traits here hold still when all strings shift their bits by one shared shuffle. A grid smooth trick bent from graph math does the lift. If a trait of this class can be probed or waved off with few probes, then its gap to the trait can also be read with few probes. Test ease and gauge ease thus stand or fall as one for this class.
Catalog record
| CREATOR | Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Amit Levi, Gopinath Mishra, Sayantan Sen |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 202 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-02235