Cover Image

The Complexity of Tensor Rank

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Schaefer, Marcus, Stefankovic, Daniel
Format:	Preprint
Published:	2016
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

How Hard is it to be a Star? Convex Geometry and the Real Hierarchy
by: Schaefer, Marcus, et al.
Published: (2025)

Beyond the Existential Theory of the Reals
by: Schaefer, Marcus, et al.
Published: (2022)

Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming
by: Alman, Josh, et al.
Published: (2023)

Critical window for approximate counting in dense Ising models
by: Galanis, Andreas, et al.
Published: (2026)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
by: Chukhin, Nikolai, et al.
Published: (2024)

Inapproximability of the independent set polynomial in the complex plane
by: Bezakova, Ivona, et al.
Published: (2017)

Low-Rank Tensor Decomposition over Finite Fields
by: Yang, Jason
Published: (2024)

The Existential Theory of the Reals as a Complexity Class: A Compendium
by: Schaefer, Marcus, et al.
Published: (2024)

The Communication Complexity of Approximating Matrix Rank
by: Sherstov, Alexander A., et al.
Published: (2024)

Devil's Games and $\text{Q}\mathbb{R}$: Continuous Games complete for the First-Order Theory of the Reals
by: Meijer, Lucas, et al.
Published: (2025)

Nearest Neighbor Complexity and Boolean Circuits
by: DiCicco, Mason, et al.
Published: (2024)

The Rank-Ramsey Problem and the Log-Rank Conjecture
by: Beniamini, Gal, et al.
Published: (2024)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
by: Hörsch, Florian, et al.
Published: (2025)

Affine Rank Minimization is ER Complete
by: Majumdar, Angshul
Published: (2026)

Lower Bounds for Approximate Sign Rank
by: Bindua, Riju, et al.
Published: (2026)

Tensor rank and dimension expanders
by: Dvir, Zeev
Published: (2025)

Strong Inapproximability for a Promise Rank Problem
by: Guruswami, Venkatesan, et al.
Published: (2026)

$\exists\mathbb{R}$-Completeness of Tensor Degeneracy and a Derandomization Barrier for Hyperdeterminants
by: Majumdar, Angshul
Published: (2026)

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

Ruling Out Low-rank Matrix Multiplication Tensor Decompositions with Symmetries via SAT
by: Yang, Jason
Published: (2024)

Structure in Communication Complexity and Constant-Cost Complexity Classes
by: Hatami, Hamed, et al.
Published: (2024)

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
by: Alman, Josh, et al.
Published: (2025)

From Proof Complexity to Circuit Complexity via Interactive Protocols
by: Arteche, Noel, et al.
Published: (2024)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
by: Zheng, Bojin, et al.
Published: (2026)

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

Pseudodeterministic Communication Complexity
by: Göös, Mika, et al.
Published: (2025)

Query Complexity with Unknowns
by: Mande, Nikhil S., et al.
Published: (2024)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
by: Nalli, Sai Soumya, et al.
Published: (2026)

The Log-Rank Conjecture: New Equivalent Formulations
by: Hambardzumyan, Lianna, et al.
Published: (2025)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
by: Eagling-Vose, Tala, et al.
Published: (2025)

The Radical Solution and Computational Complexity
by: Zheng, Bojin, et al.
Published: (2024)

The Computational Complexity of Factored Graphs
by: Gupta, Shreya, et al.
Published: (2024)

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

Random Permutations in Computational Complexity
by: Hitchcock, John M., et al.
Published: (2025)

On the Complexity of Hazard-Free Formulas
by: Arazi, Leah London, et al.
Published: (2024)

Communication Complexity is NP-hard
by: Hirahara, Shuichi, et al.
Published: (2025)

The Complexity of Order-Finding for ROABPs
by: Bhargava, Vishwas, et al.
Published: (2024)

Computational Complexity of UAP Reverse Engineering: A Formal Analysis of Automaton Identification and Data Complexity
by: Daghbouche, Karim
Published: (2025)

Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
by: Barch, Brian, et al.
Published: (2025)

Parameterized Complexity of the Star Decomposition Problem
by: Hajebi, Sahab, et al.
Published: (2024)