2026-07-23T16:50:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27058 2026-07-23T11:36:19Z ddc:004 open_access

Constant-Depth Circuits for Polynomial GCD over Any Characteristic Bhattacharjee, Somnath Kumar, Mrinal Rai, Shanthanu S. Ramanathan, Varun Saptharishi, Ramprasad Saraf, Shubhangi algebraic circuits polynomial greatest common divisor symmetric polynomials finite fields constant-depth circuits 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Somnath Bhattacharjee and Mrinal Kumar and Shanthanu S. Rai and Varun Ramanathan and Ramprasad Saptharishi and Shubhangi Saraf 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.16 urn:nbn:de:0030-drops-270580 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.16 eng https://creativecommons.org/licenses/by/4.0/legalcode