Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.23220 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918075105804288 |
|---|---|
| author | Bhattacharjee, Somnath Kumar, Mrinal Rai, Shanthanu Ramanathan, Varun Saptharishi, Ramprasad Saraf, Shubhangi |
| author_facet | Bhattacharjee, Somnath Kumar, Mrinal Rai, Shanthanu Ramanathan, Varun Saptharishi, Ramprasad Saraf, Shubhangi |
| contents | We show that the GCD of two univariate polynomials can be computed by (piece-wise) algebraic circuits of constant depth and polynomial size over any sufficiently large field, regardless of the characteristic. This extends a recent result of Andrews & Wigderson who showed such an upper bound over fields of zero or large characteristic.
Our proofs are based on a recent work of Bhattacharjee, Kumar, Rai, Ramanathan, Saptharishi \& Saraf that shows closure of constant depth algebraic circuits under factorization. On our way to the proof, we show that any $n$-variate symmetric polynomial $P$ that has a small constant depth algebraic circuit can be written as the composition of a small constant depth algebraic circuit with elementary symmetric polynomials. This statement is a constant depth version of a result of Bläser & Jindal, who showed this for algebraic circuits of unbounded depth. As an application of our techniques, we also strengthen the closure results for factors of constant-depth circuits in the work of Bhattacharjee et al. over fields for small characteristic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_23220 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constant-depth circuits for polynomial GCD over any characteristic Bhattacharjee, Somnath Kumar, Mrinal Rai, Shanthanu Ramanathan, Varun Saptharishi, Ramprasad Saraf, Shubhangi Computational Complexity We show that the GCD of two univariate polynomials can be computed by (piece-wise) algebraic circuits of constant depth and polynomial size over any sufficiently large field, regardless of the characteristic. This extends a recent result of Andrews & Wigderson who showed such an upper bound over fields of zero or large characteristic. Our proofs are based on a recent work of Bhattacharjee, Kumar, Rai, Ramanathan, Saptharishi \& Saraf that shows closure of constant depth algebraic circuits under factorization. On our way to the proof, we show that any $n$-variate symmetric polynomial $P$ that has a small constant depth algebraic circuit can be written as the composition of a small constant depth algebraic circuit with elementary symmetric polynomials. This statement is a constant depth version of a result of Bläser & Jindal, who showed this for algebraic circuits of unbounded depth. As an application of our techniques, we also strengthen the closure results for factors of constant-depth circuits in the work of Bhattacharjee et al. over fields for small characteristic. |
| title | Constant-depth circuits for polynomial GCD over any characteristic |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2506.23220 |