2026-07-22T01:28:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20428 2024-07-15T12:26:46Z ddc:004 open_access

BPL ⊆ L-AC¹ Cheng, Kuan Wang, Yichuan Randomized Space Complexity Circuit Complexity Derandomization Whether BPL = 𝖫 (which is conjectured to be equal) or even whether BPL ⊆ NL, is a big open problem in theoretical computer science. It is well known that 𝖫 ⊆ NL ⊆ L-AC¹. In this work we show that BPL ⊆ L-AC¹ also holds. Our proof is based on a new iteration method for boosting precision in approximating matrix powering, which is inspired by the Richardson Iteration method developed in a recent line of work [AmirMahdi Ahmadinejad et al., 2020; Edward Pyne and Salil P. Vadhan, 2021; Gil Cohen et al., 2021; William M. Hoza, 2021; Gil Cohen et al., 2023; Aaron (Louie) Putterman and Edward Pyne, 2023; Lijie Chen et al., 2023]. We also improve the algorithm for approximate counting in low-depth L-AC circuits from an additive error setting to a multiplicative error setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kuan Cheng and Yichuan Wang 2024 Is Part Of LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2024.32 urn:nbn:de:0030-drops-204282 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.32 eng https://creativecommons.org/licenses/by/4.0/legalcode