Image de couverture de livre

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Shpilka, Amir, Tal, Yann
Format:	Preprint
Publié:	2026
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

On Factorization of Sparse Polynomials of Bounded Individual Degree
par: Chuyoon, Aminadav, et autres
Publié: (2026)

A New Bound on Cofactors of Sparse Polynomials
par: Nahshon, Ido, et autres
Publié: (2023)

Improved Debordering of Waring Rank
par: Shpilka, Amir
Publié: (2025)

On the Complexity of Hazard-Free Formulas
par: Arazi, Leah London, et autres
Publié: (2024)

Lower Bounds for Set-Multilinear Branching Programs
par: Chatterjee, Prerona, et autres
Publié: (2023)

On Matrix Multiplication and Polynomial Identity Testing
par: Andrews, Robert
Publié: (2022)

Efficient Polynomial Identity Testing Over Nonassociative Algebras
par: Mukhopadhyay, Partha, et autres
Publié: (2025)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
par: Rajakumar, Joel, et autres
Publié: (2024)

Low-Degree Polynomials Are Good Extractors
par: Alrabiah, Omar, et autres
Publié: (2024)

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
par: Dutta, Pranjal, et autres
Publié: (2024)

Symmetric Algebraic Circuits and Homomorphism Polynomials
par: Dawar, Anuj, et autres
Publié: (2025)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
par: Yao, Penghui, et autres
Publié: (2025)

Low-Degree Testing Over Grids
par: Amireddy, Prashanth, et autres
Publié: (2023)

Optimal Depth-Three Circuits for Inner Product
par: Gurumukhani, Mohit, et autres
Publié: (2026)

Identity Testing for Circuits with Exponentiation Gates
par: Li, Jiatu, et autres
Publié: (2025)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
par: Komarath, Balagopal, et autres
Publié: (2025)

Top-Down Lower Bounds for Depth-Four Circuits
par: Göös, Mika, et autres
Publié: (2023)

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings
par: Raz, Ran
Publié: (2026)

The Quasi-Polynomial Low-Degree Conjecture is False
par: Buhai, Rares-Darius, et autres
Publié: (2025)

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
par: Gurumukhani, Mohit, et autres
Publié: (2026)

Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields
par: Dwivedi, Ashish, et autres
Publié: (2024)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
par: Bodnar, Levente
Publié: (2024)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
par: Bhargav, C. S., et autres
Publié: (2025)

A Simple Sub-Polynomial Degree Coboundary Expander
par: Hopkins, Max, et autres
Publié: (2026)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems
par: Andrews, Robert, et autres
Publié: (2024)

Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits
par: Bharadwaj, G V Sumukha, et autres
Publié: (2024)

Property Testing in Bounded Degree Hypergraphs
par: Aaronson, Hugo, et autres
Publié: (2025)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
par: Černý, Marek, et autres
Publié: (2025)

Thermodynamic Signature of Logical Depth in Quantum Circuits
par: Ibnouhsein, Issam
Publié: (2025)

Discreteness of asymptotic tensor ranks
par: Briët, Jop, et autres
Publié: (2023)

Classical Simulability of Quantum Circuits with Shallow Magic Depth
par: Zhang, Yifan, et autres
Publié: (2024)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
par: Kumar, Mrinal, et autres
Publié: (2024)

Polynomial Identity Testing via Evaluation of Rational Functions
par: Hu, Ivan, et autres
Publié: (2022)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
par: Lu, Jiaqi, et autres
Publié: (2025)

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
par: Wein, Alexander S.
Publié: (2025)

On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes
par: Drucker, Andrew, et autres
Publié: (2024)

Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
par: Nelson, Jon, et autres
Publié: (2024)

Testing Isomorphism of Graphs in Polynomial Time
par: Xue, Rui
Publié: (2023)

Identity Testing for Radical Expressions
par: Balaji, Nikhil, et autres
Publié: (2022)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
par: Sohn, Youngtak, et autres
Publié: (2025)