Distinguishability of distributions that are not close given just one sample Consider (over $n$-bit strings) the uniform distribution $U$, and another distribution $D$ such that
\begin{equation}
\text{Distance}(D, U) \geq \frac{1}{e},
\end{equation}
where $\text{Distance}$ stands for the total variation distance, given by
\begin{equation}
\text{Distance}(D, U) = \sum_{z \in \{0, 1\}^{n}} \left|\underset{\text{Z} \sim D}{\text{Pr}}[\text{Z}=z] - \underset{\text{Z} \sim U}{\text{Pr}}[\text{Z}=z]\right|,
\end{equation}
for a random variable $\text{Z}$.
In other words, $D$ and $U$ are quite far from each other. Even then, it seems intuitively true to me that we should not be able to distinguish between these two distributions with a polynomial-time algorithm if we are given one (and just one) sample as input, with the promise that the sample comes from one of these two distributions.
By this, I mean that it seems intuitive to me the quantity
\begin{equation}
\left|\underset{x \sim D}{\text{Pr}}[A(x) =1] - \underset{x \sim U}{\text{Pr}}[A(x) =1]\right|
\end{equation}
is small, for a polynomial time algorithm $A$.
Is my intuition correct? If not, it just doesn't seem obvious to me how we could distinguish these distributions with just one sample. Isn't it too little information? Can you show how we are to distinguish by any explicit description of such an algorithm for any such $D$?
Total variation distance, which is exactly half of your notion of distance, is equal to
$$
d_{TV}(D,U) = \frac{1}{2} \operatorname{Distance}(D,U) = \max_A \bigl|\Pr_{x \sim D}[A(x)] - \Pr_{x \sim U}[A(x)] \bigr|.
$$
You can take $A$ to be the indicator of $\Pr[D(x)] \geq \Pr[U(x)]$. The event $A$ might be hard to compute, but it could also be easy to compute. In the latter case, you will be able to efficiently distinguish between $D$ and $U$, even using only one sample. This may even be possible in the former case, though with an advantage less than the total variation distance.

Here is a proof of the equivalence between the two formulations.
Since
$$
\Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] =
-\left(\Pr_{x \sim D} [\overline{A(x)}] - \Pr_{x \sim U}[\overline{A(x)}]\right),
$$
where the overline represents negation, we have
$$
\delta_{TV}(D,U) = \max_A \bigl( \Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] \bigr).
$$
Let $S = \{ x : A(x) \}$. Then
$$
\Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] =
\sum_{z \in S} \bigl(\Pr_{Z \sim D}[Z = z] - \Pr_{Z \sim U}[Z = z]\bigr).
$$
This formula makes it clear that an optimal choice for $S$ is
$$
S = \{ z : \Pr_{Z \sim D}[Z = z] \geq \Pr_{Z \sim U}[Z = z] \}.
$$
For this choice of $S$, we have
\begin{align}
d_{TV}(D,U) &amp;=
\Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] \\ &amp;=
\Pr_{x \sim D}[x \in S] - \Pr_{x \sim U}[x \in S] \\ &amp;=
\bigl(1-\Pr_{x \sim D}[x \notin S]\bigr) - \bigl(1-\Pr_{x \sim U}[x \notin S]\bigr) \\ &amp;=
\Pr_{x \sim U}[x \notin S] - \Pr_{x \sim D}[x \notin S].
\end{align}
By definition of $S$, we have
\begin{align}
\Pr_{x \sim D}[x \in S] - \Pr_{x \sim U}[x \in S] &amp;=
\sum_{z \in S} \Pr_{Z \sim D}[Z = z] - \sum_{z \in S} \Pr_{Z \sim U}[Z = z] \\ &amp;=
\sum_{z \in S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr|.
\end{align}
Similarly, we have
$$
\Pr_{x \sim U}[x \notin S] - \Pr_{x \sim D}[x \notin S] =
\sum_{z \notin S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr|.
$$
It follows that
\begin{align}
\mathrm{Distance}(D,U) &amp;= 
\sum_{z \in S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr| + \sum_{z \notin S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr| \\ &amp;=
\Pr_{x \sim D}[x \in S] - \Pr_{x \sim U}[x \in S] +
\Pr_{x \sim U}[x \notin S] - \Pr_{x \sim D}[x \notin S] \\ &amp;=
2\bigl(\Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)]\bigr) \\ &amp;= 2d_{TV}(D,U).
\end{align}