BPL ⊆ L-AC¹

Kuan Cheng, Yichuan WangCCC 2024 · DOI

TL;DR

This paper proves that the complexity class BPL (randomized log-space computation) is a subset of L-AC¹ (log-uniform, constant-depth, polynomial-size circuits). This is a significant derandomization result, showing that problems solvable with a small amount of randomness and logarithmic space can be solved with deterministic circuits of very limited depth. The proof relies on a novel iteration method for boosting precision in approximating matrix powers and an improved approximate counting algorithm for AC circuits.

What Problem Does This Paper Address?

The paper tackles a fundamental question in theoretical computer science: the relationship between randomized computation and deterministic circuit complexity. Specifically, it investigates whether problems solvable by a randomized Turing machine with logarithmic space (BPL) can be solved by deterministic circuits with very limited depth (L-AC¹). While it's known that deterministic log-space computation (L) is contained within L-AC¹, the status of BPL relative to L-AC¹ was an open problem. Most researchers believe L = BPL, which would imply BPL ⊆ L-AC¹, but proving this unconditionally was challenging. This paper provides an unconditional proof of BPL ⊆ L-AC¹, a step towards understanding the power of derandomization in limited computational models.

Methods

The core of the paper's contribution lies in two main technical advancements:

  • Novel Iteration Method for Matrix Powering: The authors introduce a new iteration method for boosting the precision of approximating powers of substochastic matrices. This method is inspired by Richardson Iteration but is designed to be more efficient and to avoid the need for approximating matrix inverses, which is crucial for maintaining low circuit depth. This technique is central to the proof of BPL ⊆ L-AC¹.
  • Improved Approximate Counting for AC Circuits: The paper presents an algorithm for approximate counting in low-depth AC circuits that improves upon previous results. While prior work achieved additive error, this new algorithm achieves multiplicative error. This enhanced approximate counting capability is a key building block for the matrix approximation techniques.

The overall proof strategy involves:

  1. Establishing the improved approximate counting for AC circuits (Theorem 14).
  2. Developing the depth-efficient iteration method for matrix powering (Theorem 18).
  3. Showing how to compute the iteration step using L-uniform AC circuits (Theorem 19).
  4. Combining these to construct an AC circuit that approximates matrix powers up to a desired precision, ultimately leading to the proof of BPL ⊆ L-AC¹ (Theorem 20 and Corollary 21).

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity classes and algorithmic techniques rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Derandomization without Assumptions: The paper achieves a significant derandomization result (BPL ⊆ L-AC¹) without relying on any unproven complexity assumptions, which is a notable achievement in this area.
  • Precision Boosting in Low Depth: The core challenge in derandomizing randomized computation with limited resources (like low depth circuits) is maintaining sufficient precision. The novel iteration method effectively addresses this by allowing for precision amplification within the strict depth constraints of AC circuits.
  • Bridging Randomized Space and Deterministic Circuits: The work highlights a strong connection between randomized log-space computation and the capabilities of low-depth, deterministic circuits. It demonstrates that the randomness in BPL can be effectively eliminated by leveraging the parallel processing power of AC circuits, albeit with a sophisticated approach to precision.
  • Matrix Powering as a Central Tool: The paper frames the problem of derandomizing BPL in terms of approximating matrix powers. This perspective allows them to leverage and extend existing techniques in numerical analysis and circuit complexity.

Key Results

  • BPL ⊆ L-AC¹: The main result is the unconditional proof that the complexity class BPL is contained within L-AC¹. This means any problem solvable by a randomized log-space Turing machine can be solved by a deterministic, polynomial-size, O(log n)-depth AC circuit.
  • Multiplicative Approximate Counting: The paper provides an algorithm for approximate counting in AC circuits that achieves multiplicative error, an improvement over previous additive error results (Theorem 14).
  • Depth-Efficient Matrix Power Approximation: A key technical result is an algorithm that approximates powers of substochastic matrices using O(log n)-depth L-uniform AC circuits (Theorem 20).

Limitations and Future Work

  • Depth of AC Circuits: While the paper proves BPL ⊆ L-AC¹, the resulting AC circuits have O(log n) depth. A natural open question is whether this can be improved to O(1) or O(log log n) depth. The authors note that this would require improving the depth of approximate matrix power computations, which might be hindered by the current depth requirements of approximate counting.
  • Generalization of Iteration Method: The authors suggest that their improved iteration method for boosting precision might be applicable to other derandomization problems in space-bounded computation. They pose this as an open problem.
  • Relationship with L=BPL: The paper does not resolve the question of whether L = BPL. However, their result BPL ⊆ L-AC¹ is consistent with this conjecture.

Summary updated

BibTeX
@inproceedings{cheng2024bpl,
  author = {Kuan Cheng and Yichuan Wang},
  title = {{BPL ⊆ L-AC¹}},
  booktitle = {CCC},
  year = {2024},
  doi = {10.4230/lipics.ccc.2024.32},
}
Figure