Image de couverture de livre

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Wang, Cancan, Su, Ming, Wang, Gang, Zhang, Qingpo
Format:	Preprint
Publié:	2024
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

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
par: Bender, Matías, et autres
Publié: (2025)

Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings
par: Vu, Thi Xuan
Publié: (2025)

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

High Rate Multivariate Polynomial Evaluation Codes
par: Kopparty, Swastik, et autres
Publié: (2024)

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

Lifting with Inner Functions of Polynomial Discrepancy
par: Manor, Yahel, et autres
Publié: (2024)

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

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

On Boolean PCSPs with Polynomial Threshold Polymorphisms
par: Michno, Katzper
Publié: (2025)

Polynomial-Time PIT from (Almost) Necessary Assumptions
par: Andrews, Robert, et autres
Publié: (2025)

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
par: Chia, Nai-Hui, et autres
Publié: (2024)

One-Way Functions and Polynomial Time Dimension
par: Nandakumar, Satyadev, et autres
Publié: (2024)

Attacking the Polynomials in the Maze of Finite Fields problem
par: Barbero, Àngela, et autres
Publié: (2026)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
par: Orzel, Ian
Publié: (2025)

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

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

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

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
par: S., Karthik C., et autres
Publié: (2021)

Extractors for Polynomial Sources over $\mathbb{F}_2$
par: Chattopadhyay, Eshan, et autres
Publié: (2023)

On Efficient Noncommutative Polynomial Factorization via Higman Linearization
par: Arvind, V., et autres
Publié: (2022)

A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
par: He, Yumeng, et autres
Publié: (2024)

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
par: DeJesse, Nicholas, et autres
Publié: (2025)

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
par: Amireddy, Prashanth, et autres
Publié: (2025)

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

Optimal Polynomial-Time Estimators: A Bayesian Notion of Approximation Algorithm
par: Kosoy, Vanessa, et autres
Publié: (2016)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
par: Cai, Jin-Yi, et autres
Publié: (2024)

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

A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time"
par: Le, Tran Duy Anh, et autres
Publié: (2024)

The Entangled Quantum Polynomial Hierarchy Collapses
par: Grewal, Sabee, et autres
Publié: (2024)

Advances in List Decoding of Polynomial Codes
par: Kumar, Mrinal, et autres
Publié: (2026)

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
par: Arvind, Vikraman, et autres
Publié: (2024)

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

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
par: Przybyłek, Michał R., et autres
Publié: (2026)

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

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree
par: Shpilka, Amir, et autres
Publié: (2026)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
par: Agarwal, Avantika, et autres
Publié: (2024)

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

Polynomial Equivalence of Extended Chemical Reaction Models
par: Bajaj, Divya, et autres
Publié: (2025)

Polynomial-time completion of phylogenetic tree sets
par: Koshkarov, Aleksandr, et autres
Publié: (2026)

A Polynomial Time Algorithm for 3SAT
par: Quigley, Robert
Publié: (2024)