We establish the sample complexity of Approximate Hypothesis Testing (AHT): Unlike in classical hypothesis testing, here we are only required to approximate the sample-generating distribution rather than determine it exactly.On finite hypothesis classes, we establish that the AHT sample complexity scales inversely with the multivariate Bhattacharyya distance (3) evaluated on a set of distributions considered to be the "most confusable" w.r.t. the desired approximation accuracy.

A source sequence is to be guessed with some fidelity based on a rate-limited description of an observed sequence with which it is correlated. The tension between the description rate and the exponential growth rate of the power mean of the required number of guesses is quantified. This can be viewed as the guessing version of the classical indirect-rate-distortion problem of Dobrushin-Tsybakov’62 and Witsenhausen’80. Judicious choices of the correlated sequence, the description rate, and the fidelity criterion recover a number of recent and classical results on guessing. In the context of security, the paper provides conservative estimates on a password’s remaining security after a number of bits from a correlated database have been leaked.

A single-letter expression is provided for the exponential growth rate of the least expected number of guesses required to recover all the sequences produced by correlated memoryless sources when each guess is of a single source sequence, with the source at the guesser's discretion.

We study the guessing variants of two distributed source coding problems: the Gray-Wyner network and the Slepian-Wolf network. Building on the former, we propose a new definition of the Rényi common information as the least attainable common rate in the Gray-Wyner guessing problem under the no-excess-rate constraint. We then provide a variational characterization of this quantity. In the Slepian-Wolf setting, we follow up the work of Bracher-Lapidoth-Pfister with the case where the expected number of guesses need not converge to one but must be dominated by some given exponential.

Correlated memoryless sources produce a principal and an ancillary sequence. The exponential growth of the least expected total number of guesses required to guess the principal sequence is determined when, prior to guessing it, the guesser is allowed to produce guesses (not necessarily terminating with a correct one) of the ancillary.

Three variations on the Massey-Arikan guessing problem are considered. Their solutions provide new evidence of the duality between good guessing functions and efficient quantization schemes. They also show how type-covering can be used to provide side-information in the guessing setup.