We revisit the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, $\KpolyA$---that is, determining whether a string is ``structured" (i.e., $K^t(x) n - \log n$)---characterizes OWF,
but with either of the following caveats (1) considering a non-standard notion of \emph{probabilistic $K^t$}, as opposed to the ... more >>>

We consider interactive proofs for the promise problem, called $\epsilon$-FARNESS, in which the yes-instances are pairs of distributions over $[n]$ that are $\epsilon$-far from one another, and the no-instances are pairs of identical distributions.
For any $t\leq n^{2/3}$, we obtain an interactive proof in which the verifier has sample complexity ... more >>>

Interactive proofs of proximity for distributions, introduced by Chiesa and Gur (ITCS18) and extensively studied recently by Herman and Rothblum (STOC22, FOCS23, FOCS24}, offer a way of verifying properties of distributions using less samples than required to test these properties.

We say that such an interactive proof system is {\sf ... more >>>