betaFeedback

WorksMathematics

Exact derandomization of logarithmic space: L = RL = BPL

Abstract

We prove L=RL=BPL\mathsf L=\mathsf{RL}=\mathsf{BPL}, resolving the derandomization problem for polynomial-time randomized logarithmic space.

Introduction

A logarithmic-space machine can remember a bounded number of positions in its input, but cannot keep a polynomial-length computation or random tape. Can fresh random bits increase what such a machine can decide? We answer this question by giving a deterministic logarithmic-space simulation of every polynomial-time randomized logarithmic-space computation with bounded error.

We use machines with finite control, an endmarked read-only input, finitely many work tapes, and fresh independent fair bits. Input heads are confined between the endmarkers. All randomized running-time bounds hold on every random tape. Space counts traversed writable cells in bits, including every simultaneously live counter, numerical register and suspended call; visiting a blank work cell counts toward space. A transducer has a one-way write-only output tape. Throughout, nn is the input length and logarithms have base two.

The class L consists of languages decidable by deterministic machines in O(log⁡(n+2))O(\log(n+2)) work space. Such a halting deterministic machine has only polynomially many configurations and hence runs in polynomial time. The class RL permits polynomial-time randomized machines in this space, with acceptance probability zero on no inputs and at least 1/21/2 on yes inputs. For BPL, the corresponding probabilities are at most 1/31/3 and at least 2/32/3.

Theorem 1.1 (Exact logarithmic-space derandomization).

L=RL=BPL.\mathrm{L} = \mathrm{RL} = \mathrm{BPL}.

The proof approximates arbitrary acceptance probabilities. This gives the two-sided statement directly, and also applies to computations whose acceptance probabilities have no decision gap. Its quantitative form separates the memory needed for the input from the memory needed for the requested accuracy.

Theorem 1.2 (Acceptance-probability approximation). Fix a randomized machine M\mathcal{M} with polynomial worst-case running time and O(log⁡(n+2))O(\log(n+2)) work space. Let pM(x)p_{\mathcal{M}}(x) be its acceptance probability on an input xx of length nn. There is a uniform deterministic algorithm which, on input (x,1q)(x,1^q) with q≥1q \ge1, outputs an integer 0≤a≤2q+20 \le a \le2^{q+2} satisfying

∣a2−(q+2)−pM(x)∣≤2−q.\left|a2^{-(q+2)} - p_{\mathcal{M}}(x)\right| \le2^{-q}.

It uses O(log⁡(n+2)+q)O(\log(n+2)+q) work space and (n+2)O(1)2O(q)(n+2)^{O(1)}2^{O(q)} time. The constants depend only on M\mathcal{M}.

In particular, every fixed inverse-polynomial accuracy is attained in logarithmic space and polynomial time. The precision parameter is unary; the running-time bound is exponential in general qq. We first prove the fixed inverse-polynomial result and then obtain the single variable-precision algorithm by padding. Section 12 also derives total deterministic separators for bounded-error promise problems and constructs accepting runs when the machine’s acceptance probability has a specified inverse-polynomial lower bound.

The simulation is also effective at the level of machine descriptions. Given a source program and supplied polynomial-time and logarithmic-space bounds, one terminating compiler produces a deterministic decider and explicit numerical bounds for its space and time (Theorem 13.1). The supplied bounds are hypotheses on the source, rather than properties the compiler must decide. Section 13 constructs this compiler by specializing one fixed deterministic library.

Historical context

The complexity of probabilistic Turing machines was developed by Gill [18], including measures of both time and tape usage. Random walks made the logarithmic-space question concrete: Aleliunas, Karp, Lipton, Lovász and Rackoff obtained polynomial-time randomized algorithms for undirected connectivity and explicitly asked whether polynomial-time randomized logarithmic space could be simulated in deterministic logarithmic space [3]. Early work also studied probabilistic machines without a polynomial-time restriction. Borodin, Cook and Pippenger obtained a quadratic-space deterministic simulation in this broader setting [7]. The distinction between a space bound and simultaneous time and space bounds is essential throughout this history.

Pseudorandom generators attack the problem by replacing a long sequence of fresh random bits with the output generated from a short seed. Ajtai, Komlós and Szemerédi gave early logarithmic-space constructions that hit small-space tests using short random strings [2]. Babai, Nisan and Szegedy subsequently obtained pseudorandom generators through multiparty communication bounds [6]. Nisan’s generator uses O(Slog⁡R)O(S \log R) seed bits for a space-SS computation reading RR random bits [21]. For logarithmic space and polynomially many bits this gives O(log⁡2n)O(\log^{2} n) seed length; direct seed enumeration has a quasipolynomial time bound. Nisan’s later simultaneous simulation achieves polynomial time and O(log⁡2n)O(\log^{2} n) space [22]. Although its title uses RL, that result includes two-sided bounded error. For S(n)≥log⁡nS(n) \ge\log n, Nisan and Zuckerman showed that a space-SS computation using poly⁡(S)\operatorname{poly}(S) random bits can be simulated using only O(S)O(S) random bits and O(S)O(S) space [24]. The restriction on the original number of random bits is substantive; for logarithmic space it permits polylogarithmically many bits.

Saks and Zhou reduced the deterministic space needed for general bounded-error logarithmic-space computation to O(log⁡3/2n)O(\log^{3/2} n) [31]. Cai, Chakaravarthy and van Melkebeek established a simultaneous tradeoff: for each fixed rational 0≤α≤1/20 \le\alpha\le1/2, the simulation uses time nO(log⁡1/2−αn)n^{O(\log^{1/2-\alpha} n)} and space O(log⁡3/2+αn)O(\log^{3/2+\alpha} n) [10]. The polynomial-time endpoint has squared-logarithmic space. Hoza subsequently improved the general space bound to O(log⁡3/2n/log⁡log⁡n)O(\log^{3/2} n/\sqrt{\log\log n}) [19], Theorem 1.6 and Corollary A.5. These smaller space containments do not assert the same polynomial-time endpoint. Hoza’s work also develops weighted pseudorandomness, in which signed or real weights replace an ordinary probability distribution; the space-containment improvement and the new weighted-generator construction are distinct results of that paper.

Acceptance-probability estimation also connects derandomization to stochastic matrix products and inverses. Ahmadinejad, Kelner, Murtagh, Peebles, Sidford and Vadhan developed high-precision small-space algorithms for random-walk probabilities, with stronger bounds for Eulerian graphs [1]. Cohen, Doron, Sberlo and Ta-Shma later used varying precision across recursion to improve the space complexity of long stochastic matrix products [16]. The construction below works with a finite inverse on a time-layered configuration graph; its correction and copy hierarchy controls the information retained while individual entries are evaluated.

Structural restrictions on a computation provide another route. For undirected connectivity, Nisan, Szemerédi and Wigderson obtained deterministic space O(log⁡3/2n)O(\log^{3/2} n) [23], subsequently improved to O(log⁡4/3n)O(\log^{4/3} n) by Armoni, Ta-Shma, Wigderson and Zhou [4]. Reingold’s logarithmic-space algorithm, whose conference version appeared at STOC 2005, settles undirected connectivity [27, 28]. Reingold, Trevisan and Vadhan studied regular directed graphs and gave logarithmic-space path search for Eulerian directed graphs [29]. Their oblivious walk constructions impose additional labeling conditions. General directed configuration graphs need not have these properties, so those results did not settle the unrestricted randomized computation problem. A read-once branching program is a layered deterministic computation that reads the input symbols once in a fixed order (bits in the binary case). Its length is the number of steps, and its width is the largest number of states in a layer. A 1/21/2-hitting set for a class of programs contains an accepting input for every member that accepts at least half of all input strings. The relation between one-sided and two-sided derandomization also requires care. Cheng and Hoza proved that one uniformly logarithmic-space-enumerable 1/21/2-hitting-set family for all width-nn, length-nn read-once branching programs would yield L=BPL\mathrm{L} = \mathrm{BPL} [13]. The premise is a hitting-set construction; it is not merely the language-class equality RL=L\mathrm{RL} = \mathrm{L}.

Recent results refine both general and structured models. Chen, Cohen, Doron, Khaskelberg and Ta-Shma improve error reduction for weighted generators; in the polynomial-width regime their construction has seed length log⁡∣Σ∣+O(log⁡2T+log⁡(1/δ))\log|\Sigma| + O(\log^{2} T + \log(1/\delta)), where TT is branching-program length, Σ\Sigma its alphabet and δ\delta the error [12]. Cheng and Wu obtain simultaneous polynomial-time and polylogarithmic-space simulations for regular branching programs, with extensions to polynomial-time randomized logarithmic-space machines whose two-way read-only random tape visits each cell at most constantly often, and to such machines with read-once randomness and an auxiliary stack whose push, pop and idle schedule is independent of the random bits. Consecutive stays on a random-tape cell count as one visit [14] Theorems 5–6. Hardness-versus-randomness approaches additionally give conditional, certified and per-instance alternatives; Pyne and Tell survey this line of work [26].

Effectivity has its own substantial antecedents. Pyne, Raz and Zhan construct a universal deterministic estimator whose O(S(n))O(S(n)) space guarantee follows from prBPL⊆SPACE[O(S(n))]\mathrm{prBPL} \subseteq\mathrm{SPACE}[O(S(n))], for space-constructible S(n)≥log⁡nS(n) \ge\log n [25] full version, Theorem 5.1. Here prBPL\mathrm{prBPL} denotes promise problems solvable in polynomial time and randomized logarithmic space with bounded error. The compiler below uses a fixed separator established in this paper and supplies explicit source-specific numerical resource bounds. Its construction should be read in this context of universal simulation, with the source bounds supplied as part of the compiler input.

Proof strategy

Fix a randomized machine and an input of length nn, and write B=Θ(log⁡(n+2))B = \Theta(\log(n + 2)). The proof constructs a finite family of estimates of its acceptance probability, indexed by O(B)O(B)-bit descriptions. More than three quarters of these estimates are accurate; every member of the family can be evaluated by a halting deterministic computation using O(B)O(B) space. Exhaustive enumeration then gives a deterministic answer. The second guarantee is essential: enumeration must finish even on choices for which the estimate is inaccurate.

The exact target. The configuration reduction of Section 2 gives a strictly forward substochastic matrix SS on a polynomial-size set V0V_0 and a vector e∈{0,1}V0e \in\{0,1\}^{V_0} indicating accepting final configurations. The vector

p0=(I−S)−1ep_0 = (I-S)^{-1}e

records acceptance probabilities from all configurations. The inverse is a finite sum, because every transition advances time. Section 4 replaces SS successively by transitions ClC_l on sets VlV_l of configuration copies, carrying accumulated rewards Wl∈[0,1]VlW_l \in[0,1]^{V_l}. Each copy step has a designated primary copy. If zlz_l is obtained from the original start x0x_0 by always choosing that copy, then

0≤p0(x0)−Wl(zl)≤∣V0∣2−(H−1)l,0 \le p_0(x_0) - W_l(z_l) \le|V_0|2^{-(H-1)l},

where H≥4H \ge4 is fixed. Thus L=O(B)L = O(B) stages make WL(zL)W_L(z_L) accurate to any fixed inverse-polynomial error. Every stage has at most N=2CNBN = 2^{C_N B} vertices for a fixed constant CNC_N.

From the estimator to a deterministic decision. The algorithm estimates WLW_L in one shared finite random environment σ\sigma. Its law is uniform on a specified finite set of matrix-and-bit-string encodings of length O(B)O(B). On each channel a retention test selects vertices; write Xf(v)X_f(v) for the indicator that vv is retained at the final stage rate f=2−HLf = 2^{-HL}, and πf\pi_f for its probability. Section 3 gives πf≍f\pi_f \asymp f. Theorem 9.8 proves, for the actual estimator W‾L\overline{W}_L,

1NEσ∑v∈VLXf(v)f∣W‾L(v)−WL(v)∣8≤C82−8p.\frac{1}{N}\mathbb{E}_{\sigma}\sum_{v\in V_L}\frac{X_f(v)}{f}\left|\overline{W}_L(v)-W_L(v)\right|^8 \leq C^8 2^{-8p}.

Here pp is the statistical accuracy exponent. Keeping only the summand at zLz_L gives

E[∣W‾L(zL)−WL(zL)∣8∣Xf(zL)=1]≤NfπfC82−8p.\mathbb{E}\left[\left|\overline{W}_L(z_L)-W_L(z_L)\right|^8 \mid X_f(z_L)=1\right] \leq N\frac{f}{\pi_f}C^8 2^{-8p}.

The factor NN is the price of passing from the integrated bound to one specified start. Since log⁡N=O(B)\log N = O(B), taking the estimator’s statistical budget to be a sufficiently large fixed multiple of BB makes pp large enough to pay this price and gives an accurate value on more than three quarters of the conditional environments.

The implementation computes dyadic approximations to the same fixed value W‾L(zL)\overline{W}_L(z_L) on every environment. Numerical precision changes the requested digits, not the lists and ports defining that value. Choosing the stage count, statistical budget and digit accuracy makes the total error less than 1/81/8 on more than three quarters of the encodings conditioned on Xf(zL)=1X_f(z_L)=1. Their median has the same error bound. We enumerate the original encodings with their original multiplicities, so the multiset reproduces exactly this conditional law.

Repeated enumeration finds the median while retaining only the current encoding and O(B)O(B)-bit numerical and counting registers. Every digit query used here requests one of the first O(B)O(B) binary places, terminates in O(B)O(B) space, and confines its physical input heads between the real endmarkers. It therefore has only 2O(B)2^{O(B)} complete configurations and takes at most that many steps. There are also 2O(B)2^{O(B)} encodings, so the entire computation takes polynomial time. Comparing its answer with 1/21/2 distinguishes acceptance probabilities at most 1/31/3 from those at least 2/32/3. This proves the nontrivial containment in Theorem 1.1.

Why the hierarchy can be estimated. The hierarchy reduces transition entries more rapidly than it increases the number of vertices incident to positive entries. A correction EE replaces CC by D=C−E+ECD=C-E+EC, with

I−D=(I+E)(I−C).I-D=(I+E)(I-C).

This identity transfers the removed transition contribution into the reward. Detectors identify columns with many substantial entries and suppress correction there. The copy step distributes the remaining large entries while controlling how many vertices are incident to them. An ordered-support argument gives a factorial truncation bound, so only constantly many correction steps are needed at each stage.

The exact matrices and conditional expectations define the targets; they are not stored. Section 5 represents their contributions by sample-dependent tables with bounded row support. Corrections also have bounded incoming degree. Their true conditional means recover the required entries. The algorithm substitutes earlier estimates into these formulas, so the analysis must bound the resulting bias without assuming that the estimated factors are independent. Conditional averaging preserves the specified source and endpoint retention tests. Its uniform mixing bound is derived from classical property (T) results of Shalom [33]; Section 6 proves the finite-action and sampling consequences used here.

At parent budget MM, Section 7 averages differences between child estimates at consecutive budgets mm and m−1m-1. These differences have small norm because both approximate the same true sample term. Their contributions at the same endpoint are combined before measuring the difference. The slack M−mM-m has two roles: it determines the length of conditional averaging available to reduce the noise, and it bounds the description of an immediate sample path. Grouping comparable slacks lets Section 8 replace each row array by a short list of exceptions to a common default. The proof charges deterministic conditional-mean error separately from residual noise.

A product follows a correction edge to an intermediate vertex and then queries a right factor there. Releasing the old source changes the weighted error domain. Bounded incoming degree controls that change, and the task’s accuracy assignment pays the resulting factor. Thus the same construction that permits a source address to be discarded also appears explicitly in the error analysis.

Why the lists fit in logarithmic space. A list entry is found by a path. Retaining a full endpoint at every recursive level would cost too much. Section 9 therefore compares endpoints by short fingerprint keys at small slacks, combining polynomial evaluation and affine hashing [32, 11]. Candidate endpoints can depend on earlier comparisons, so a fixed-pair collision estimate alone is insufficient. A comparison calculation using exact equality within one budget block produces candidate sets independent of that block’s fingerprint bits. Smooth support functions charge paths that leave these sets to lower-call errors; collisions within the fixed sets supply the remaining error. This coupled induction proves the moment bound for the actual estimator.

Sections 10 and 11 establish its total space bound. Numerical operations request one bounded digit at a time. The controller keeps one vertex cursor, uses bounded inverse ports for correction moves, and recovers incoming accesses by traversing finite program trees, using the contour idea of Cook and McKenzie [17] and the space-preserving traversal perspective of Lange, McKenzie and Tapp [20]. A shared catalytic bit vector permits fingerprint comparisons without keeping a key index at every recursive level. The controller assigns each call a decreasing recursion allowance ww, with top allowance O(B)O(B), and uses the requested digit place tt as its numerical clock. If the child has allowance w′w' and digit place jj, all local data retained during that call occupy at most

A(w−w′)+D(t−j)A(w-w') + D(t-j)

bits, including the controller copies used by a traversal. The child clock may increase only in proportion to the decrease of allowance. These differences telescope along the active call chain; the environment, cursor, catalyst and scratch are shared once. The bound and termination do not depend on statistical accuracy.

Section 12 carries out the median construction for fixed inverse-polynomial error and derives the class equality and promise separation. It then obtains one algorithm for all unary precision requests by padding, and constructs certified accepting computations when the machine’s acceptance probability has an inverse-polynomial lower bound. Section 13 is a separate application of fixed-precision approximation: one resource-capped universal interpreter yields a fixed deterministic library, whose syntactic specialization supplies explicit resource bounds for each source machine.

The transition model and resource parameters

We first express acceptance probability as a finite matrix inverse. Time labels make the transition matrix nilpotent; keeping the complete configuration at each vertex gives local access in both directions. The construction will use the resulting probability vector at every configuration, as well as its value at the designated start.

A matrix indexed by a finite set VV is strictly forward if there is an integer time attached to every vertex and every nonzero entry goes to a strictly later time. It is substochastic if its entries are nonnegative and each row sums to at most one. An edge is specified by a vertex and a port from a fixed finite set. A paired edge operation returns the other endpoint together with its inverse port; applying the inverse operation restores the first endpoint. Absent ports are explicitly recognized.

Lemma 2.1 (Configuration reduction). Fix a polynomial-time randomized machine using O(log⁡(n+2))O(\log(n+2)) work space. On an input of length nn one can specify, uniformly in logarithmic space, a polynomial-size vertex set V0V_0, a strictly forward substochastic matrix SS, a vector e∈{0,1}V0e \in\{0,1\}^{V_0}, and a start vertex x0x_0 with the following properties.

  1. The incoming and outgoing port degrees of SS are bounded by constants depending only on the machine. Port validity, edge weights, and pairing are computable in logarithmic space.

  1. The vector p0=(I−S)−1ep_0=(I-S)^{-1}e is well defined and belongs to [0,1]V0[0,1]^{V_0}.

  1. The coordinate p0(x0)p_0(x_0) is the acceptance probability of the machine.

In particular, an RL computation gives the promise p0(x0)=0p_0(x_0)=0 or p0(x0)≥1/2p_0(x_0)\ge1/2.

Proof. Let T(n)T(n) be a fixed polynomial upper bound on the running time. A vertex records a time in {0,…,T(n)}\{0,\ldots,T(n)\}, the finite control, all input and work head positions, and the contents of a sufficiently large box of O(log⁡(n+2))O(\log(n+2)) work cells. Take elementary machine steps with fixed dyadic coin probabilities. A transition advances the time by one. Invalid configurations or moves leaving the box have no corresponding transition. The box is chosen large enough that this never affects a computation from the specified start.

References

  1. [1]AmirMahdi Ahmadinejad, Jonathan Kelner, Jack Murtagh, John Peebles, Aaron Sidford, and Salil Vadhan. High-precision estimation of random walks in small space. In 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020), pages 1295–1306. IEEE, 2020. Full version: arXiv:1912.04524.arxiv.org/abs/1912.04524
  2. [2]Miklós Ajtai, János Komlós, and Endre Szemerédi. Deterministic simulation in LOGSPACE. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 132–140. Association for Computing Machinery, 1987.DOI
  3. [3]Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science, pages 218–223. IEEE, 1979.DOI
  4. [4]Roy Armoni, Amnon Ta-Shma, Avi Wigderson, and Shiyu Zhou. An O(log(n)^{4/3}) space algorithm for (s,t) connectivity in undirected graphs. Journal of the ACM, 47(2):294–311, 2000.DOI
  5. [5]Algirdas Avizienis. On a flexible implementation of digital computer arithmetic. In C. M. Popplewell, editor, Information Processing 1962, pages 664–670. North-Holland, 1963.
  6. [6]László Babai, Noam Nisan, and Márió Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. Journal of Computer and System Sciences, 45(2):204–232, 1992.DOI
  7. [7]Allan Borodin, Stephen Cook, and Nicholas Pippenger. Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and Control, 58(1–3):113–136, 1983.DOI
  8. [8]Mark Braverman, Gil Cohen, and Sumegha Garg. Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs. SIAM Journal on Computing, 49(5):STOC18–242–STOC18–299, 2020.DOI
  9. [9]Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, and Florian Speelman. Computing with a full memory: Catalytic space. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 857–866. Association for Computing Machinery, 2014.
  10. [10]Jin-Yi Cai, Venkatesan T. Chakaravarthy, and Dieter van Melkebeek. Time-space tradeoff in derandomizing probabilistic logspace. Theory of Computing Systems, 39(1):189–208, 2006.
  11. [11]J. Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143–154, 1979.DOI
  12. [12]Ben Chen, Gil Cohen, Dean Doron, Yuval Khas​​kelberg, and Amnon Ta-Shma. Improved error reduction for weighted PRGs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026), volume 392 of Leibniz International Proceedings in Informatics, pages 39:1–39:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026.
  13. [13]Kuan Cheng and William M. Hoza. Hitting sets give two-sided derandomization of small space. Theory of Computing, 18(21):1–32, 2022.
  14. [14]Kuan Cheng and Ruiyang Wu. SC derandomization for regular ROBPs and models beyond BPL, 2026. Version 1, September 20, 2026.
  15. [15]Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma. Error reduction for weighted PRGs against read once branching programs. In 36th Computational Complexity Conference (CCC 2021), volume 200 of Leibniz International Proceedings in Informatics, pages 22:1–22:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.
  16. [16]Gil Cohen, Dean Doron, Ori Sberlo, and Amnon Ta-Shma. Approximating iterated multiplication of stochastic matrices in small space. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 35–45. Association for Computing Machinery, 2023.
  17. [17]Stephen A. Cook and Pierre McKenzie. Problems complete for deterministic logarithmic space. Journal of Algorithms, 8(3):385–394, 1987.DOI
  18. [18]John Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6(4):675–695, 1977.
  19. [19]William M. Hoza. Better pseudodistributions and derandomization for space-bounded computation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 of Leibniz International Proceedings in Informatics, pages 28:1–28:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.
  20. [20]Klaus-Jörn Lange, Pierre McKenzie, and Alain Tapp. Reversible space equals deterministic space. Journal of Computer and System Sciences, 60(2):354–367, 2000.
  21. [21]Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992.
  22. [22]Noam Nisan. RL ⊆ SC. Computational Complexity, 4(1):1–11, 1994.
  23. [23]Noam Nisan, Endre Szemerédi, and Avi Wigderson. Undirected connectivity in O(log^{1.5} n) space. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, FOCS ’92, pages 24–29. IEEE Computer Society, 1992.
  24. [24]Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43–52, 1996.
  25. [25]Edward Pyne, Ran Raz, and Wei Zhan. Certified hardness vs. randomness for log-space. In 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2023), pages 989–1007. IEEE, 2023. Full version: arXiv:2303.16413.arxiv.org/abs/2303.16413
  26. [26]Edward Pyne and Roei Tell. Using hardness vs randomness to design low-space algorithms. Electronic Colloquium on Computational Complexity, Report TR26-045, 2026.
  27. [27]Omer Reingold. Undirected ST-connectivity in log-space. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, pages 376–385. ACM, 2005.DOI
  28. [28]Omer Reingold. Undirected connectivity in log-space. Journal of the ACM, 55(4):17:1–17:24, 2008.DOI
  29. [29]Omer Reingold, Luca Trevisan, and Salil Vadhan. Pseudorandom walks on regular digraphs and the RL vs. L problem. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 457–466. Association for Computing Machinery, 2006.
  30. [30]Marcel Riesz. Sur les maxima des formes bilinéaires et sur les fonctionnelles linéaires. Acta Mathematica, 49:465–497, 1927.
  31. [31]Michael Saks and Shiyu Zhou. BP_HSPACE(S) ⊆ DSPACE(S^{3/2}). Journal of Computer and System Sciences, 58(2):376–403, 1999.
  32. [32]Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701–717, 1980.DOI
  33. [33]Yehuda Shalom. Bounded generation and Kazhdan’s property (T). Publications Mathématiques de l’IHÉS, 90:145–168, 1999.DOI
  34. [34]G. O. Thorin. Convexity theorems generalizing those of M. Riesz and Hadamard with some applications. PhD thesis, Lund University, 1948. Russian translation by Yu. T. Medvedev, Matematika 1 (1957), no. 3, 43–78. Translation and bibliographic record.

Paper details

vlnc:W_mrevxazv
Version
v2 · latest
Published
License
LicenseRef-OpenAI-public
Usage

views · 30

downloads · 3

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

unreleased internal OpenAI model

View statement
Looking for related papers…
Contents