Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits

Pranjal Dutta, Prateek Dwivedi, Nitin SaxenaCCC 2021

TL;DR

This paper introduces novel deterministic algorithms for Polynomial Identity Testing (PIT) on specific types of depth-4 arithmetic circuits. They achieve the first polynomial-time whitebox PIT for $\Sigma^{[k]}\Pi\Sigma\Lambda$ circuits and the first quasipolynomial-time blackbox PIT for both $\Sigma^{[k]}\Pi\Sigma\Lambda$ and $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ circuits, tackling long-standing open problems in algebraic complexity.

What Problem Does This Paper Address?

Polynomial Identity Testing (PIT) is a fundamental problem in computer science: given an arithmetic circuit, determine if it computes the identically zero polynomial. While efficient PIT algorithms exist for many circuit classes, certain restricted depth-4 circuits have remained challenging. Specifically, the paper focuses on $\Sigma^{[k]}\Pi\Sigma\Lambda$ and $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ circuits. These models, while seemingly simple, have resisted efficient PIT algorithms, particularly in the whitebox setting for $\Sigma^{[k]}\Pi\Sigma\Lambda$ and in the blackbox setting for both. Solving PIT for these circuits is significant because it has implications for derandomizing general PIT and understanding the power of restricted circuit classes. The paper aims to close these gaps by providing the first efficient deterministic PIT algorithms for these specific depth-4 circuit families.

Methods

The paper introduces a novel technique called DiDI (Divide and Derive) for whitebox PIT. This inductive approach reduces the top $\Pi$-gate of a $\Sigma^{[k]}\Pi\Sigma\Lambda$ circuit to a $\Lambda$-gate by repeatedly dividing by one of the terms and then taking a derivative with respect to a new variable. This process effectively reduces the fan-in of the top gate at each step, eventually leading to a simpler problem that can be solved using existing PIT algorithms.

For the blackbox PIT results, the authors leverage the Jacobian criterion and faithful homomorphisms. The Jacobian matrix captures algebraic independence, and a carefully constructed homomorphism can reduce the number of variables in the circuit while preserving its non-zero properties. This reduction allows for efficient PIT on the transformed circuit. The power series expansion of certain expressions is also a key analytical tool used to handle the complexities arising from divisions and derivatives.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • DiDI Technique: The core innovation is the DiDI technique, which cleverly uses division and differentiation to reduce the complexity of $\Sigma^{[k]}\Pi\Sigma\Lambda$ circuits. This is a significant departure from previous methods and offers a new perspective on tackling these circuit classes.
  • Logarithmic Derivative as a Tool: The logarithmic derivative, $\frac{d \log f}{dx} = \frac{df/dx}{f}$, proves to be a powerful analytical tool. It linearizes products and helps in transforming complex circuit structures into more manageable forms, particularly when combined with power series expansions.
  • Jacobian for Variable Reduction: The Jacobian matrix, a standard tool in algebraic geometry, is effectively used to identify algebraically independent components of the circuit. This allows for a reduction in the number of variables, a crucial step for achieving quasipolynomial time complexity in the blackbox setting.
  • Bridging Whitebox and Blackbox: The paper demonstrates how techniques developed for whitebox PIT (like DiDI) can inspire or be adapted for blackbox settings, and vice-versa, highlighting the interconnectedness of these problem variants.

Key Results

  • First Polynomial-Time Whitebox PIT for $\Sigma^{[k]}\Pi\Sigma\Lambda$: The paper provides a deterministic whitebox PIT algorithm for $\Sigma^{[k]}\Pi\Sigma\Lambda$ circuits with a time complexity of $s^{O(k^{7k})}$, where $s$ is the circuit size. This is a significant improvement over previous results, which were either exponential in $k$ or did not exist for $k \ge 3$.
  • First Quasipolynomial-Time Blackbox PIT for $\Sigma^{[k]}\Pi\Sigma\Lambda$ and $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$: The authors present quasipolynomial-time blackbox PIT algorithms for both $\Sigma^{[k]}\Pi\Sigma\Lambda$ (with complexity $s^{O(k \log \log s)}$) and $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ (with complexity $s^{O(\delta^2 k \log s)}$). These results are important for their respective circuit classes, especially for $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ where even $d=2$ was a challenging open problem.

Limitations and Future Work

  • Exponential Dependence on $k$: The whitebox PIT for $\Sigma^{[k]}\Pi\Sigma\Lambda$ has an exponential dependence on $k$ ($s^{O(k^{7k})}$). An open question is whether this exponent can be improved, perhaps to $O(k)$.
  • Blackbox PIT for $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$: While quasipolynomial-time blackbox PIT is achieved for $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$, improving this to polynomial time remains an open problem.
  • Generalization to Other Models: The paper suggests that the DiDI technique might be applicable to other circuit models, and it raises questions about efficient PIT for $\Sigma\Pi\Sigma\text{M}_2$ circuits (involving bivariate polynomials) and for rational functions.
  • Characteristic of the Field: The results generally hold for fields of large characteristic. Further investigation into how these algorithms behave over finite fields of small characteristic might be warranted.

Summary updated

BibTeX
@inproceedings{dutta2021deterministic,
  author = {Pranjal Dutta and Prateek Dwivedi and Nitin Saxena},
  title = {{Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits}},
  booktitle = {CCC},
  year = {2021},
}
Figure