{"id":"openai-math/Exact-Derandomization-of-Logarithmic-Space-L-equals-RL-equals-BPL","pdf":"https://github.com/openai/math/blob/main/preprints/Exact-Derandomization-of-Logarithmic-Space-L-equals-RL-equals-BPL-September-23-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Exact-Derandomization-of-Logarithmic-Space-L-equals-RL-equals-BPL-September-23-2026","tags":["computational-complexity","derandomization","logspace"],"score":0,"title":"Exact derandomization of logarithmic space: L = RL = BPL","domain":"Theoretical computer science","family":"103","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We prove $`\\mathsf L=\\mathsf{RL}=\\mathsf{BPL}`$, resolving the derandomization problem for polynomial-time randomized logarithmic space.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":1,"published":"2026-09-23","reactions":{},"discussion":[{"url":"https://scottaaronson.blog/?p=10169#:~:text=Though%20its%20truth%20was%20never%20in%20serious%20doubt%2C%20there%20was%20a%20whole%20subcommunity%20focused%20on%20proving%20this.","date":"2026-10-07","kind":"web","site":"Shtetl-Optimized","text":"Though its truth was never in serious doubt, there was a whole subcommunity focused on proving this. The Fourier Transform and integer multiplication in less than O(n log n) time, breaking a barrier that had stood since the 1960s. The new running time, if you’re curious, is O(n log 0.9999999999999…","added":"2026-10-24","title":"The Mathocalypse"}],"formalized":true,"family_title":"Exact derandomization of logarithmic space: $`\\mathsf L=\\mathsf{RL}=\\mathsf{BPL}`$"}