Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.06569 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912225092960256 |
|---|---|
| author | Bharadwaj, G V Sumukha Raja, S |
| author_facet | Bharadwaj, G V Sumukha Raja, S |
| contents | We address the black-box polynomial identity testing (PIT) problem for non-commutative polynomials computed by $+$-regular circuits, a class of homogeneous circuits introduced by [AJMR](STOC 2017, Theory of Computing 2019). These circuits can compute polynomials with a number of monomials that are doubly exponential in the circuit size. They gave an efficient randomized PIT algorithm for +-regular circuits of depth 3 and posed the problem of developing an efficient black-box PIT for higher depths as an open problem.
We present a randomized black-box polynomial-time algorithm for +-regular circuits of any constant depth. Specifically, our algorithm runs in $s^{O(d^2)}$ time, where $s$ and $d$ represent the size and the depth of the $+$-regular circuit, respectively. We combine several key techniques in a novel way. We employ a nondeterministic substitution automaton that transforms the polynomial into a structured form and utilizes polynomial sparsification along with commutative transformations to maintain non-zeroness. Additionally, we introduce matrix composition, coefficient modification via the automaton, and multi-entry outputs-methods that have not previously been applied in the context of black-box PIT. Together, these techniques enable us to effectively handle exponential degrees and doubly exponential sparsity in non-commutative settings, enabling polynomial identity testing for higher-depth circuits. Our work resolves an open problem from [AJMR].
In particular, we show that if $f$ is a non-zero non-commutative polynomial in $n$ variables over the field $\mathbb{F}$, computed by a depth-$d$ $+$-regular circuit of size $s$, then $f$ cannot be a polynomial identity for the matrix algebra $\mathbb{M}_{N}(\mathbb{F})$, where $N= s^{O(d^2)}$ and the size of the field $\mathbb{F}$ depending on the degree of $f$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_06569 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits Bharadwaj, G V Sumukha Raja, S Computational Complexity We address the black-box polynomial identity testing (PIT) problem for non-commutative polynomials computed by $+$-regular circuits, a class of homogeneous circuits introduced by [AJMR](STOC 2017, Theory of Computing 2019). These circuits can compute polynomials with a number of monomials that are doubly exponential in the circuit size. They gave an efficient randomized PIT algorithm for +-regular circuits of depth 3 and posed the problem of developing an efficient black-box PIT for higher depths as an open problem. We present a randomized black-box polynomial-time algorithm for +-regular circuits of any constant depth. Specifically, our algorithm runs in $s^{O(d^2)}$ time, where $s$ and $d$ represent the size and the depth of the $+$-regular circuit, respectively. We combine several key techniques in a novel way. We employ a nondeterministic substitution automaton that transforms the polynomial into a structured form and utilizes polynomial sparsification along with commutative transformations to maintain non-zeroness. Additionally, we introduce matrix composition, coefficient modification via the automaton, and multi-entry outputs-methods that have not previously been applied in the context of black-box PIT. Together, these techniques enable us to effectively handle exponential degrees and doubly exponential sparsity in non-commutative settings, enabling polynomial identity testing for higher-depth circuits. Our work resolves an open problem from [AJMR]. In particular, we show that if $f$ is a non-zero non-commutative polynomial in $n$ variables over the field $\mathbb{F}$, computed by a depth-$d$ $+$-regular circuit of size $s$, then $f$ cannot be a polynomial identity for the matrix algebra $\mathbb{M}_{N}(\mathbb{F})$, where $N= s^{O(d^2)}$ and the size of the field $\mathbb{F}$ depending on the degree of $f$. |
| title | Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2411.06569 |