2 papers
cs.DS2024
Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space
Christian Janos Lebeda, Jakub Tětek
Suppose we have a sample from a distribution and we want to test whether for a fixed distribution . Specifically, we want to reject with constant probability, if…
cs.DS2021
Better Sum Estimation via Weighted Sampling
Lorenzo Beretta, Jakub Tětek
Given a large set where each item has weight , we want to estimate the total weight to within factor of with some consta…