Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-048 | 4th March 2024 09:55

$BPL\subseteq L-AC^1$

RSS-Feed




TR24-048
Authors: Kuan Cheng, Yichuan Wang
Publication: 10th March 2024 06:54
Downloads: 547
Keywords: 


Abstract:

Whether $BPL=L$ (which is conjectured to be equal), or even whether $BPL\subseteq NL$, is a big open problem in theoretical computer science. It is well known that $L-NC^1\subseteq L\subseteq NL\subseteq L-AC^1$. In this work we will show that $BPL\subseteq L-AC^1$, which was not known before. Our proof is based on modifying the Richardson Iteration method for boosting precision in approximating matrix powering, which was developed in a line of works [AKM+20][PV21][CDR+21][CDST22][PP22][CHT+23]. We also improve the algorithm for approximating counting in low-depth $L$-uniform $AC$ circuit from additive error setting to multiplicative error setting.



ISSN 1433-8092 | Imprint