DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.16

Constant-Depth Circuits for Polynomial GCD over Any Characteristic

Authors: Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

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.

Cite as

Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf. Constant-Depth Circuits for Polynomial GCD over Any Characteristic. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhattacharjee_et_al:LIPIcs.CCC.2026.16,
  author =	{Bhattacharjee, Somnath and Kumar, Mrinal and Rai, Shanthanu S. and Ramanathan, Varun and Saptharishi, Ramprasad and Saraf, Shubhangi},
  title =	{{Constant-Depth Circuits for Polynomial GCD over Any Characteristic}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{16:1--16:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.16},
  URN =		{urn:nbn:de:0030-drops-270580},
  doi =		{10.4230/LIPIcs.CCC.2026.16},
  annote =	{Keywords: algebraic circuits, polynomial greatest common divisor, symmetric polynomials, finite fields, constant-depth circuits}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.24

Exponential Lower Bounds via Exponential Sums

Authors: Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta, and Saswata Mukherjee

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

Valiant’s famous VP vs. VNP conjecture states that the symbolic permanent polynomial does not have polynomial-size algebraic circuits. However, the best upper bound on the size of the circuits computing the permanent is exponential. Informally, VNP is an exponential sum of VP-circuits. In this paper we study whether, in general, exponential sums (of algebraic circuits) require exponential-size algebraic circuits. We show that the famous Shub-Smale τ-conjecture indeed implies such an exponential lower bound for an exponential sum. Our main tools come from parameterized complexity. Along the way, we also prove an exponential fpt (fixed-parameter tractable) lower bound for the parameterized algebraic complexity class VW⁰_{nb}[𝖯], assuming the same conjecture. VW⁰_{nb}[𝖯] can be thought of as the weighted sums of (unbounded-degree) circuits, where only ± 1 constants are cost-free. To the best of our knowledge, this is the first time the Shub-Smale τ-conjecture has been applied to prove explicit exponential lower bounds. Furthermore, we prove that when this class is fpt, then a variant of the counting hierarchy, namely the linear counting hierarchy collapses. Moreover, if a certain type of parameterized exponential sums is fpt, then integers, as well as polynomials with coefficients being definable in the linear counting hierarchy have subpolynomial τ-complexity. Finally, we characterize a related class VW[𝖥], in terms of permanents, where we consider an exponential sum of algebraic formulas instead of circuits. We show that when we sum over cycle covers that have one long cycle and all other cycles have constant length, then the resulting family of polynomials is complete for VW[𝖥] on certain types of graphs.

Cite as

Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta, and Saswata Mukherjee. Exponential Lower Bounds via Exponential Sums. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bhattacharjee_et_al:LIPIcs.ICALP.2024.24,
  author =	{Bhattacharjee, Somnath and Bl\"{a}ser, Markus and Dutta, Pranjal and Mukherjee, Saswata},
  title =	{{Exponential Lower Bounds via Exponential Sums}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.24},
  URN =		{urn:nbn:de:0030-drops-201677},
  doi =		{10.4230/LIPIcs.ICALP.2024.24},
  annote =	{Keywords: Algebraic complexity, parameterized complexity, exponential sums, counting hierarchy, tau conjecture}
}

Search Results

Documents authored by Bhattacharjee, Somnath

Constant-Depth Circuits for Polynomial GCD over Any Characteristic

Abstract

Cite as

Exponential Lower Bounds via Exponential Sums

Abstract

Cite as

Thanks for your feedback!

Could not send message