Deterministic Depth-4 PIT and Normalization
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908406209576960 |
|---|---|
| author | Guo, Zeyu Wang, Siki |
| author_facet | Guo, Zeyu Wang, Siki |
| contents | In this paper, we initiate the study of deterministic PIT for $Σ^{[k]}ΠΣΠ^{[δ]}$ circuits over fields of any characteristic, where $k$ and $δ$ are bounded. Our main result is a deterministic polynomial-time black-box PIT algorithm for $Σ^{[3]}ΠΣΠ^{[δ]}$ circuits, under the additional condition that one of the summands at the top $Σ$ gate is squarefree.
Our techniques are purely algebro-geometric: they do not rely on Sylvester--Gallai-type theorems, and our PIT result holds over arbitrary fields.
The core of our proof is based on the normalization of algebraic varieties. Specifically, we carry out the analysis in the integral closure of a coordinate ring, which enjoys better algebraic properties than the original ring. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_15143 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Deterministic Depth-4 PIT and Normalization Guo, Zeyu Wang, Siki Computational Complexity Algebraic Geometry In this paper, we initiate the study of deterministic PIT for $Σ^{[k]}ΠΣΠ^{[δ]}$ circuits over fields of any characteristic, where $k$ and $δ$ are bounded. Our main result is a deterministic polynomial-time black-box PIT algorithm for $Σ^{[3]}ΠΣΠ^{[δ]}$ circuits, under the additional condition that one of the summands at the top $Σ$ gate is squarefree. Our techniques are purely algebro-geometric: they do not rely on Sylvester--Gallai-type theorems, and our PIT result holds over arbitrary fields. The core of our proof is based on the normalization of algebraic varieties. Specifically, we carry out the analysis in the integral closure of a coordinate ring, which enjoys better algebraic properties than the original ring. |
| title | Deterministic Depth-4 PIT and Normalization |
| topic | Computational Complexity Algebraic Geometry |
| url | https://arxiv.org/abs/2504.15143 |