Buchumschlag

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Arvind, Vikraman, Joglekar, Pushkar S
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On Efficient Noncommutative Polynomial Factorization via Higman Linearization
von: Arvind, V., et al.
Veröffentlicht: (2022)

Trading Determinism for Noncommutativity in Edmonds' Problem
von: Arvind, V., et al.
Veröffentlicht: (2024)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
von: Arvind, V., et al.
Veröffentlicht: (2023)

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials
von: Wang, Cancan, et al.
Veröffentlicht: (2024)

A Quadratic Lower Bound for Noncommutative Circuits
von: Shastri, Pratik
Veröffentlicht: (2026)

New Hardness Results for Low-Rank Matrix Completion
von: Chawin, Dror, et al.
Veröffentlicht: (2025)

Exploring the Reductions Between SSP-NP-complete Problems and Developing a Compendium Website Displaying the Results
von: Pfaue, Femke
Veröffentlicht: (2024)

Derandomizing Isolation In Catalytic Logspace
von: Arvind, V., et al.
Veröffentlicht: (2025)

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
von: Dutta, Pranjal, et al.
Veröffentlicht: (2024)

The Complexity of Tensor Rank
von: Schaefer, Marcus, et al.
Veröffentlicht: (2016)

The Rank-Ramsey Problem and the Log-Rank Conjecture
von: Beniamini, Gal, et al.
Veröffentlicht: (2024)

A Compendium of Reductions: reductions.network
von: Grüne, Christoph, et al.
Veröffentlicht: (2025)

New Hardness Results for the LOCAL Model via a Simple Self-Reduction
von: Balliu, Alkida, et al.
Veröffentlicht: (2025)

Affine Rank Minimization is ER Complete
von: Majumdar, Angshul
Veröffentlicht: (2026)

Lower Bounds for Approximate Sign Rank
von: Bindua, Riju, et al.
Veröffentlicht: (2026)

Strong Inapproximability for a Promise Rank Problem
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2026)

Recovery Reductions, Conjectures, and Barriers
von: Nareddy, Tejas, et al.
Veröffentlicht: (2025)

Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing
von: Courtney, Joshua M.
Veröffentlicht: (2026)

Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction
von: Delavenne, Hugo, et al.
Veröffentlicht: (2024)

Low-Rank Tensor Decomposition over Finite Fields
von: Yang, Jason
Veröffentlicht: (2024)

Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming
von: Alman, Josh, et al.
Veröffentlicht: (2023)

Reductions Between Code Equivalence Problems
von: Cheraghchi, Mahdi, et al.
Veröffentlicht: (2025)

Higher Hardness Results for the Reconfiguration of Odd Matchings
von: Dorfer, Joseph
Veröffentlicht: (2026)

On a Hierarchy of Spectral Invariants for Graphs
von: Arvind, V., et al.
Veröffentlicht: (2023)

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
von: Alman, Josh, et al.
Veröffentlicht: (2025)

High Rate Multivariate Polynomial Evaluation Codes
von: Kopparty, Swastik, et al.
Veröffentlicht: (2024)

What Juris Hartmanis taught me about Reductions
von: Immerman, Neil
Veröffentlicht: (2024)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
von: Chukhin, Nikolai, et al.
Veröffentlicht: (2024)

Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing
von: Courtney, Joshua M.
Veröffentlicht: (2026)

The Log-Rank Conjecture: New Equivalent Formulations
von: Hambardzumyan, Lianna, et al.
Veröffentlicht: (2025)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
von: Ostonov, Azimkhon, et al.
Veröffentlicht: (2024)

A Subexponential Reduction from Product Partition to Subset Sum
von: Costandin, Marius
Veröffentlicht: (2024)

Improved Debordering of Waring Rank
von: Shpilka, Amir
Veröffentlicht: (2025)

Complexity Results of Persuasion
von: Grastien, Alban
Veröffentlicht: (2025)

Rank Bounds and PIT for $Σ^3 ΠΣΠ^d$ circuits via a non-linear Edelstein-Kelly theorem
von: Garg, Abhibhav, et al.
Veröffentlicht: (2025)

Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings
von: Vu, Thi Xuan
Veröffentlicht: (2025)

Maximum Matching and Related Problems in Catalytic Logspace
von: Chakraborty, Srijan, et al.
Veröffentlicht: (2026)

The Communication Complexity of Approximating Matrix Rank
von: Sherstov, Alexander A., et al.
Veröffentlicht: (2024)

On Formally Undecidable Propositions of Nondeterministic Complexity and Related Classes
von: Kolář, Martin
Veröffentlicht: (2026)

A Courcelle-Type Metatheorem for Rank-Bounded Unconstrained Binary Optimization
von: Harary, Marc
Veröffentlicht: (2025)