Towards deterministic algorithms for constant-depth factors of constant-depth circuits

DOI10.1145/3778245MaRDI QIDQ7228641zbMATH OpenFDO

Authors Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk

Publication date 14 April 2026

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3778245

zbMATH Keywords

constant-depth algebraic circuitsderandomizationpolynomial factorizationpolynomial identity testing

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• A super-polynomial lower bound for regular arithmetic formulas
• Completeness and reduction in algebraic complexity theory
• Decoding of Reed Solomon codes beyond the error-correction bound
• Derandomizing multivariate polynomial factoring for low degree factors
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Deterministic divisibility testing via shifted partial derivatives
• Deterministic factorization of sparse polynomials with bounded individual degree
• Equivalence of polynomial identity testing and polynomial factorization
• Factoring polynomials with rational coefficients
• Factorization of polynomials given by arithmetic branching programs
• Hardness-randomness tradeoffs for bounded depth arithmetic circuits
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• Modern computer algebra
• On the relation between polynomial identity testing and finding variable disjoint factors
• Superpolynomial lower bounds against low-depth algebraic circuits

This page was built for publication: Towards deterministic algorithms for constant-depth factors of constant-depth circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7228641)