Search for: All records

The classical coding theorem in Kolmogorov complexity states that if an n-bit string x is sampled with probability δ by an algorithm with prefix-free domain then K(x) ≤ log(1/δ) + O(1). In a recent work, Lu and Oliveira [31] established an unconditional time-bounded version of this result, by showing that if x can be efficiently sampled with probability δ then rKt(x) = O(log(1/δ)) + O(log n), where rKt denotes the randomized analogue of Levin’s Kt complexity. Unfortunately, this result is often insufficient when transferring applications of the classical coding theorem to the time-bounded setting, as it achieves a O(log(1/δ)) bound instead of the information-theoretic optimal log(1/δ). Motivated by this discrepancy, we investigate optimal coding theorems in the time-bounded setting. Our main contributions can be summarised as follows. • Efficient coding theorem for rKt with a factor of 2. Addressing a question from [31], we show that if x can be efficiently sampled with probability at least δ then rKt(x) ≤ (2 + o(1)) · log(1/δ) +O(log n). As in previous work, our coding theorem is efficient in the sense that it provides a polynomial-time probabilistic algorithm that, when given x, the code of the sampler, and δ, it outputs, with probability ≥ 0.99, a probabilistic representation of x that certifies this rKt complexity bound. • Optimality under a cryptographic assumption. Under a hypothesis about the security of cryptographic pseudorandom generators, we show that no efficient coding theorem can achieve a bound of the form rKt(x) ≤ (2 − o(1)) · log(1/δ) + poly(log n). Under a weaker assumption, we exhibit a gap between efficient coding theorems and existential coding theorems with near-optimal parameters. • Optimal coding theorem for pKt and unconditional Antunes-Fortnow. We consider pKt complexity [17], a variant of rKt where the randomness is public and the time bound is fixed. We observe the existence of an optimal coding theorem for pKt, and employ this result to establish an unconditional version of a theorem of Antunes and Fortnow [5] which characterizes the worst-case running times of languages that are in average polynomial-time over all P-samplable distributions. 

The Antarctic Circumpolar Current (ACC) represents the world’s largest ocean-current system and affects global ocean circulation, climate and Antarctic ice-sheet stability^1–3. Today, ACC dynamics are controlled by atmospheric forcing, oceanic density gradients and eddy activity⁴. Whereas palaeoceanographic reconstructions exhibit regional heterogeneity in ACC position and strength over Pleistocene glacial–interglacial cycles^5–8, the long-term evolution of the ACC is poorly known. Here we document changes in ACC strength from sediment cores in the Pacific Southern Ocean. We find no linear long-term trend in ACC flow since 5.3 million years ago (Ma), in contrast to global cooling⁹and increasing global ice volume¹⁰. Instead, we observe a reversal on a million-year timescale, from increasing ACC strength during Pliocene global cooling to a subsequent decrease with further Early Pleistocene cooling. This shift in the ACC regime coincided with a Southern Ocean reconfiguration that altered the sensitivity of the ACC to atmospheric and oceanic forcings^11–13. We find ACC strength changes to be closely linked to 400,000-year eccentricity cycles, probably originating from modulation of precessional changes in the South Pacific jet stream linked to tropical Pacific temperature variability¹⁴. A persistent link between weaker ACC flow, equatorward-shifted opal deposition and reduced atmospheric CO₂during glacial periods first emerged during the Mid-Pleistocene Transition (MPT). The strongest ACC flow occurred during warmer-than-present intervals of the Plio-Pleistocene, providing evidence of potentially increasing ACC flow with future climate warming.