Characterizing the Distinguishability of Product Distributions through Multicalibration

Given a sequence of samples x1, dots , xk promised to be drawn from one of two distributions X0, X1, a well-studied problem in statistics is to decide textitwhich distribution the samples are from. Information theoretically, the maximum advantage in distinguishing the two distributions given k samples is captured by the total variation distance between X0otimes k and X1otimes k. However, when we restrict our attention to textitefficient distinguishers (i.e., small circuits) of these two distributions, exactly characterizing the ability to distinguish X0otimes k and X1otimes k is more involved and less understood. In this work, we give a general way to reduce bounds on the computational indistinguishability of X0 and X1 to bounds on the textitinformation-theoretic indistinguishability of some specific, related variables widetildeX0 and widetildeX1. As a consequence, we prove a new, tight characterization of the number of samples k needed to efficiently distinguish X0otimes k and X1otimes k with constant advantage as [ k = Thetaleft(dH-2left(widetildeX0, widetildeX1right)right), ] which is the inverse of the squared Hellinger distance dH between two distributions widetildeX0 and widetildeX1 that are computationally indistinguishable from X0 and X1. Likewise, our framework can be used to re-derive a result of Halevi and Rabin (TCC 2008) and Geier (TCC 2022), proving nearly-tight bounds on how computational indistinguishability scales with the number of samples for arbitrary product distributions.