CS Paper Radar

Simulating Space Bounded Read-$k$ PTMs with Space Bounded Read-Once PTMs

Kuan Cheng, Shengtang Huang, Ruiyang Wu

cs.CC ·submitted 2026-11-13 03:16 UTC · v3

Abstract

We show that read-$k$ Probabilistic Turing Machines with bounded space $S$ and running time $T$ can be simulated by read-once Probabilistic Turing Machines with error $\varepsilon$, running in space $ O(k^2 (S + \log (n+ T)) + \log (1/ε))$ and time $\frac{1}{\varepsilon} \cdot 2^{O\left(k^2\left(S+\log(n+T) \right)\right)}$. As a direct consequence we show that read-$k$ $\mathsf{BPL}$ is equal to $\mathsf{BPL}$, for any constant $k$. Recently OpenAI announced that $\mathsf{BPL} = \mathsf{L}$. If this is true then our result immediately implies that read-$k$ $\mathsf{BPL}$ is equal to $\mathsf{L}$.

Closest papers

Nearest neighbours by meaning across the whole index.

Unconditional Separation between LL and CLL

cs.CC ·2026-10-11 ·Shubham Bhardwaj
publishedtheory similarity 0.62
Abstract · 11 pages. v2: fixed an error in the upper bound concerning the endmarkers of the catalytic tape; thanks to András Salamon for pointing it ou…

Catalytic computation involves the study of Turing machines that are provided an additional catalytic tape (with arbitrary content) that the machine may use while ensuring that the tape contents are restored at the end of the computation. Although it is known that catalytic log-space machines are at least as powerful as non-deterministic log-space (and more), we do not have unconditional asymptotic separations. In this work, we prove an unconditional separation between a deterministic space complexity class and its catalytic counterpart. More precisely, at the doubly logarithmic scale, we show that catalytic Turing machines can provably compute more languages than standard deterministic doubly-logarithmic space machines. The separation is witnessed by the unary language $\mathrm{POW2} = \{1^n : n \text{ is a power of two}\}$. We construct a catalytic Turing machine that uses $O(\log \log n)$ bits of space and $O(\log n)$ bits of catalytic tape to decide $\mathrm{POW2}$, whereas any standard deterministic Turing machine requires $Ω(\log n)$ space to decide it.

0.30

SC Derandomization for Regular ROBPs and Models Beyond BPL

cs.CC ·2026-09-20 ·Kuan Cheng, Ruiyang Wu
similarity 0.60
Abstract

We study SC derandomizations for regular read-once branching programs (ROBPs) and computation models beyond BPL. For regular ROBPs with length $n$, width $w$, and multiple accept nodes, we attain the following results. 1. When $n \le w$, we show an SC derandomization with space $O(\log^2 n+\log w)$ and two-sided error $1/\text{poly}(nw)$. 2. When $n \ge w$, we show an SC derandomization with space $O(\log n \log w)$ and two-sided error $1/\text{poly}(w)$. In addition, when $w=O(\log n)$, we attain an optimal $O(\log n)$ space derandomization with two-sided error $1/\text{poly}(w)$. 3. When $w \le 2^{O(\sqrt{\log n})}$, we show that reachability of regular ROBPs (i.e. derandmization of one-sided unbounded small error ROBPs) can be computed in SC. We also show that when regular ROBPs are powering, optimal deterministic logspace can be attained for computing reachability and for bounded two-sided error derandomization, when $w = n^{1/c}$ for some constant $c$. We further show that two super sets of BPL can be computed in SC. 1. For probabilistic logspace TMs with a two-way access random tape, we show that it can be approximated in SC if each entry of the random tape is accessed for at most a constant number of times. 2. For probabilistic logspace TMs with a polynomial size stack, i.e. probabilistic logspace Auxiliary Push-down Machines (AuxPDMs), we show that it can be approximated in SC if the timings of push/pop/idle stack operations do not depend on the randomness. The first model is the read-multiplicity model considered by Impagliazzo, Nisan, Wigderson (STOC'94), in which they show that their INW generator can fool such computations. For the second model, we indicate that it contains candidate languages separating BQL from BPL considered by Apers and Edenhofer (CCC'25).

0.44

Simulating Nondeterministic Turing Machines in Subexponential Deterministic Time

cs.CC ·2026-11-09 ·Carmen Strassle, Bernardo Subercaseaux
similarity 0.58
Abstract

We show that every multitape nondeterministic Turing machine can be simulated deterministically in subexponential time. Specifically, we show that the recent algorithms for $3$-$\mathsf{SAT}$ presented by OpenAI and Anthropic imply $\mathsf{NTIME}[t]\subseteq\mathsf{DTIME}[2^{O(t \log \log t/\sqrt{\log t})}]$, and that a stronger consequence of their proof yields \[\mathsf{NTIME}[t] \subseteq\mathsf{DTIME}[2^{O(t /\sqrt{\log t})}]. \] More generally, we show that any subexponential time algorithm for solving circuit-CSPs transfers to a deterministic simulation of $\mathsf{NTIME}$ with the same savings. Our results follow from new generalizations of Cook--Levin, which may be of independent interest.

0.15

Internalizing Chain-of-thought into Looped Transformers

cs.CC cs.DScs.LG ·2026-10-19 ·Kehang Zhou, Pinyan Lu
similarity 0.57
Abstract · 20 pages, 1 figure

Chain-of-thought (CoT) enables constant-bit-size transformers to perform general-purpose computation through generated tokens (Li and Wang, 2025a), whereas looped transformers carry out the same computation by recurrence in hidden states (latent thought). We construct a family of constant-bit-size looped transformers that interpolates between CoT and latent thought. For a prescribed loop count $L=L(n)$ and a fixed integer $k\ge1$ satisfying $s(n)^{1/k}=Ω(L)$, our transformer simulates a time-$t(n)$, space-$s(n)$ Turing machine using a context window of $O(s(n)/L)$ and $O(t(n)s(n)^{1/k}/L)$ generated tokens, reducing both resources by a factor of $L$ relative to the corresponding unlooped queue-machine simulation. The construction also holds with softmax attention at constant bit-size, under the finite-precision kernel specified in this paper.

0.20

Accepting-Path Counting at the One-Tape $n\log n$ Threshold

cs.CC ·2026-09-26 ·Ondřej Kuželka
theory similarity 0.56
Abstract · 9 pages

We observe that the classical $n\log n$ time threshold for one-tape Turing machines is also a threshold for their accepting-path counts. Below it, every nondeterministic one-tape machine running in strong $o(n\log n)$ time has a rational ordinary generating function of accepting-path counts. At strong $O(n\log n)$ time, the situation changes completely: there is a fixed one-tape machine whose accepting-path function is complete for $\#\mathsf P_1$, the tally analogue of $\#\mathsf P$, under parsimonious polynomial-time tally reductions. A second construction within the same time bound gives positive accepting-path counts with a noncomputable exponential growth rate. The rationality result combines the one-tape time gap with the linear-time counting theorem of Tadaki, Yamakami and Lin. The completeness proof adapts the linear-time universal counting machine of Beame et al. to the one-tape setting.

0.32

Beyond the Static Barrier for Ordinary Dynamic Approximate Membership

cs.DS cs.CCcs.IT ·2026-08-23 ·Qizhi Chen, Zhebei Shen, Zhehan Yu
theory similarity 0.56
Abstract

We prove a strict space separation between static and ordinary dynamic approximate membership at every fixed error rate. For each fixed $\varepsilon\in(0,1)$, a capacity-$n$ ordinary dynamic filter over a universe of size $u$, with zero false negatives, pointwise false-positive probability at most $\varepsilon$, arbitrary history dependence, a free public random tape, and at most $H$ bits of persistent state, satisfies \[ H\ge \bigl(\log_2(1/\varepsilon)+a_\varepsilon^{\rm c}\bigr)n-o(n), \] under only $u/n\to\infty$. The constant $a_\varepsilon^{\rm c}$ is an explicit variational threshold obtained by preserving the dependence between the parent accepted mass and the successor reservoir. The structural step is a common-continuation transport lemma. A joint posterior KL bound gives a branch-specific survivor support; the same legal delete--insert word transports that support to one successor state, forcing an accepted reservoir. We then keep the parent outside mass $1-X$ in the conditional-entropy argument instead of replacing it by $1-\varepsilon$. This yields a two-variable analytic envelope, with no selected thresholds, dyadic witnesses, or numerical assumptions.

0.23

A First-Order Entropy Law for Canonical T-Complexity of Finite-Alphabet i.i.d. Sources

cs.IT math.ST ·2026-08-18 ·Thomas Schürmann
theory similarity 0.55
Abstract · 10 pages, no figures

Let $W_N$ be an exact length-$N$ block from a strictly positive i.i.d. source $\mathbf p$ on a fixed finite alphabet. We prove that the canonical T-complexity $c_T$ satisfies \[ \frac{c_T(W_N)}{e^{-γ}h(\mathbf p) N/\log N}\longrightarrow1 \] in probability and in $L^r$ for every fixed $1\le r<\infty$, where $h(\mathbf p)$ is the source entropy in nats and $γ$ is the Euler-Mascheroni constant. The proof combines an exact length budget for canonical recovery, a critical-scale $E_1$ estimate for an ideal backward chain, and an exact finite-block boundary representation. An exact Doob-transform identity expresses the finite-boundary law relative to the ideal law conditioned at each step to avoid the current history-dependent successor codeword. A history-uniform renewal estimate then makes the telescoping endpoint density uniformly asymptotic to one, so no one-step approximation errors accumulate.

0.40

Upper and Lower Bounds on the Space Complexity of Multi-word Single-Writer Registers

cs.DC ·2026-08-19 ·Yuanhao Wei, Yousof Yavari
theory similarity 0.55
Abstract · Full version of paper appearing in DISC'26

We prove matching upper and lower bounds on the space complexity of simulating a large shared register using smaller shared registers. We focus on the case where both the simulated and base registers are single-writer, which means they can be accessed concurrently by multiple readers but only by a single writer. To strengthen our lower bounds, we prove that they hold even when the base registers are atomic and the simulated register is regular. Furthermore, the lower bounds hold for obstruction-free implementations, which means they also hold for lock-free and wait-free implementations. If $m$ is the number of values representable by the large register and $b$ is the number of values representable by each base register, our first lower bound says that any obstruction-free implementation that has an invisible reader requires at least $\lceil \frac{m-1}{b-1} \rceil$ base registers. A reader is considered invisible if it never writes to base registers. This lower bound is asymptotically tight for the invisible-reader case and represents an exponential improvement over the previous best known lower bound. For the general case, which allows any combination of visible and invisible readers, we prove a $\lceil \min(\frac{m-1}{b-1}, r+\frac{\log{m}}{\log{b}}) \rceil$ space lower bound, where $r$ is the number of readers. To show that this lower bound is asymptotically tight, we develop a wait-free algorithm for simulating a multi-word atomic register from atomic base registers using $Θ(r + \frac{\log{m}}{\log{b}})$ space. Combining this algorithm with known invisible-reader constructions gives a $Θ(\min(\frac{m}{b}, r + \frac{\log{m}}{\log{b}}))$ space upper bound. This improves upon the previously known space upper bound of $Θ(\min(\frac{m}{b}, r\frac{\log{m}}{\log{b}}))$.

0.32