Black-Box Identity Testing for Unmixed ΣΠΣΠ(k) Circuits

Polynomial Identity Testing (PIT) is a fundamental problem in computer science, asking if a given polynomial is identically zero. It's crucial for various applications, from primality testing to proving complexity class relationships like IP=PSPACE.

While randomized polynomial-time algorithms for PIT exist (Schwartz-Zippel Lemma), derandomizing them or finding deterministic polynomial-time solutions remains a major open challenge. This paper tackles a restricted, yet significant, circuit class.

The focus is on low-degree unmixed Sigma-Pi-Sigma-Pi (Sigma-Pi-Sigma-Pi(k)) circuits. These are depth-4 arithmetic circuits where the multiplication gates at the second level have 'unmixed' variables, meaning each factor depends on a single variable.

Specifically, an unmixed circuit C = Sum(Fi) where Fi = Product(fij(xj)) means each fij is a univariate polynomial. This structure is key to developing deterministic algorithms, as general depth-4 circuits are notoriously difficult to handle.

The paper presents the first polynomial-time black-box identity testing algorithm for these low-degree unmixed Sigma-Pi-Sigma-Pi(k) circuits. 'Black-box' means the algorithm only queries the circuit for output values, without inspecting its internal structure.

The core of the approach involves two main steps: 1) Proving a sparsity bound for these circuits. It's shown that a special class of these circuits, if they compute the zero polynomial, are 'sparse' in a quantifiable way, specifically s^O(k^2)-sparse.

Sparsity refers to the number of non-zero monomials in a polynomial. This bound is crucial because it limits the complexity of the polynomial, making it amenable to deterministic testing methods. The proof uses induction and careful analysis of subcircuits.

2. Constructing a polynomial-size 'hitting set' based on this sparsity result. A hitting set is a collection of points such that if a non-zero polynomial evaluates to zero at all points in the set, then the polynomial must be identically zero.

The algorithm constructs this hitting set in polynomial time. To test if a circuit C is identically zero, one simply evaluates C at each point in the hitting set. If all evaluations are zero, then C is identically zero; otherwise, it is not.

This work partly answers a question posed by Saxena, contributing to the broader effort of derandomizing PIT for restricted circuit classes. Understanding these specific models can provide insights for tackling the general PIT problem.

The significance lies in providing a deterministic solution where previously only randomized or non-black-box methods were known for this specific circuit family. This advances our understanding of the computational complexity of polynomials.

An open problem remains: designing a polynomial-time black-box identity testing algorithm for general low-degree Sigma-Pi-Sigma-Pi(k) circuits, without the 'unmixed' variable restriction. This would be a significant breakthrough in the field.