Copertina

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Wang, Cancan, Su, Ming, Wang, Gang, Zhang, Qingpo
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
di: Bender, Matías, et al.
Pubblicazione: (2025)

Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings
di: Vu, Thi Xuan
Pubblicazione: (2025)

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
di: Dutta, Pranjal, et al.
Pubblicazione: (2024)

High Rate Multivariate Polynomial Evaluation Codes
di: Kopparty, Swastik, et al.
Pubblicazione: (2024)

A New Bound on Cofactors of Sparse Polynomials
di: Nahshon, Ido, et al.
Pubblicazione: (2023)

Lifting with Inner Functions of Polynomial Discrepancy
di: Manor, Yahel, et al.
Pubblicazione: (2024)

Symmetric Algebraic Circuits and Homomorphism Polynomials
di: Dawar, Anuj, et al.
Pubblicazione: (2025)

On Matrix Multiplication and Polynomial Identity Testing
di: Andrews, Robert
Pubblicazione: (2022)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
di: Michno, Katzper
Pubblicazione: (2025)

Polynomial-Time PIT from (Almost) Necessary Assumptions
di: Andrews, Robert, et al.
Pubblicazione: (2025)

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
di: Chia, Nai-Hui, et al.
Pubblicazione: (2024)

One-Way Functions and Polynomial Time Dimension
di: Nandakumar, Satyadev, et al.
Pubblicazione: (2024)

Attacking the Polynomials in the Maze of Finite Fields problem
di: Barbero, Àngela, et al.
Pubblicazione: (2026)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
di: Orzel, Ian
Pubblicazione: (2025)

On Factorization of Sparse Polynomials of Bounded Individual Degree
di: Chuyoon, Aminadav, et al.
Pubblicazione: (2026)

Low-Degree Polynomials Are Good Extractors
di: Alrabiah, Omar, et al.
Pubblicazione: (2024)

Efficient Polynomial Identity Testing Over Nonassociative Algebras
di: Mukhopadhyay, Partha, et al.
Pubblicazione: (2025)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
di: S., Karthik C., et al.
Pubblicazione: (2021)

Extractors for Polynomial Sources over $\mathbb{F}_2$
di: Chattopadhyay, Eshan, et al.
Pubblicazione: (2023)

On Efficient Noncommutative Polynomial Factorization via Higman Linearization
di: Arvind, V., et al.
Pubblicazione: (2022)

A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
di: He, Yumeng, et al.
Pubblicazione: (2024)

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
di: DeJesse, Nicholas, et al.
Pubblicazione: (2025)

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
di: Amireddy, Prashanth, et al.
Pubblicazione: (2025)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
di: Yao, Penghui, et al.
Pubblicazione: (2025)

Optimal Polynomial-Time Estimators: A Bayesian Notion of Approximation Algorithm
di: Kosoy, Vanessa, et al.
Pubblicazione: (2016)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
di: Cai, Jin-Yi, et al.
Pubblicazione: (2024)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
di: Komarath, Balagopal, et al.
Pubblicazione: (2025)

A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time"
di: Le, Tran Duy Anh, et al.
Pubblicazione: (2024)

The Entangled Quantum Polynomial Hierarchy Collapses
di: Grewal, Sabee, et al.
Pubblicazione: (2024)

Advances in List Decoding of Polynomial Codes
di: Kumar, Mrinal, et al.
Pubblicazione: (2026)

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
di: Arvind, Vikraman, et al.
Pubblicazione: (2024)

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings
di: Raz, Ran
Pubblicazione: (2026)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
di: Przybyłek, Michał R., et al.
Pubblicazione: (2026)

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

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree
di: Shpilka, Amir, et al.
Pubblicazione: (2026)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
di: Agarwal, Avantika, et al.
Pubblicazione: (2024)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
di: Bhargav, C. S., et al.
Pubblicazione: (2025)

Polynomial Equivalence of Extended Chemical Reaction Models
di: Bajaj, Divya, et al.
Pubblicazione: (2025)

Polynomial-time completion of phylogenetic tree sets
di: Koshkarov, Aleksandr, et al.
Pubblicazione: (2026)

A Polynomial Time Algorithm for 3SAT
di: Quigley, Robert
Pubblicazione: (2024)