{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreianmqcvj57dsnnhtim6hwredtnjztnjiifd6hk7bet6onzeys7t5u",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3meynm75syyl2"
  },
  "path": "/report/2026/021",
  "publishedAt": "2026-02-16T15:31:48.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "Symmetry of Information (SoI) is a fundamental result in Kolmogorov complexity stating that for all $n$-bit strings $x$ and $y$, $K(x,y) = K(y) + K(x \\mid y)$ up to an additive error of $O(\\log n)$ [ZL70]. In contrast, understanding whether SoI holds for time-bounded Kolmogorov complexity measures is closely related to longstanding open problems in complexity theory and cryptography, such as the P versus NP question [LW95, Hir22] and the existence of one-way functions [HILNO23, HLO24, HLN24]. In this paper, we prove that SoI fails for $rKt$ complexity, the randomized analogue of Levin's $Kt$ complexity [Lev84]. This is the first unconditional result of this type for a randomized notion of time-bounded Kolmogorov complexity. More generally, we establish a close relationship between the validity of SoI for $rKt$ and the existence of randomized algorithms approximating $rKt(x)$. Motivated by applications in cryptography, we also establish the failure of SoI for a related notion called $pKt$ complexity [HLO24], and provide an extension of the results to the average-case setting. Finally, we prove a near-optimal lower bound on the complexity of estimating conditional $rKt$, a result that might be of independent interest. Our findings complement those of [Ron04], who demonstrated the failure of SoI for $Kt$ complexity. In contrast, the randomized setting poses a significant challenge, which we overcome using insights from [KK25], structural results about $rKt$ implied by SoI, and techniques from meta-complexity [Oli19] and the theory of computational pseudorandomness [TV07].",
  "title": "TR26-021 |  Failure of Symmetry of Information for Randomized Computations | \n\n\tJinqiao Hu, \n\n\tYahel Manor, \n\n\tIgor Oliveira"
}