Distance Estimation for High-Dimensional Discrete Distributions

Given two distributions P and Q over a high-dimensional domain 0,1n, and a parameter varepsilon, the goal of distance estimation is to determine the statistical distance between P and Q, up to an additive tolerance ± varepsilon. Since exponential lower bounds (in n) are known for the problem in the standard sampling model, research has focused on richer query models where one can draw conditional samples. This paper presents the first polynomial query distance estimator in the conditional sampling model (mathsfCOND). We base our algorithm on the relatively weaker textitsubcube conditional sampling (mathsfSUBCOND) oracle, which draws samples from the distribution conditioned on some of the dimensions. mathsfSUBCOND is a promising model for widespread practical use because it captures the natural behavior of discrete samplers. Our algorithm makes tildeO(n3/varepsilon5) queries to mathsfSUBCOND.