:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Yang, Jason
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2401.06857
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

The Complexity of Tensor Rank
by: Schaefer, Marcus, et al.
Published: (2016)

Faster search for tensor decomposition over finite fields
by: Yang, Jason
Published: (2025)

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

New results in canonical polyadic decomposition over finite fields
by: Yang, Jason
Published: (2025)

Fixed-parameter tractability of canonical polyadic decomposition over finite fields
by: Yang, Jason
Published: (2024)

Depth-first search for tensor rank and border rank over finite fields
by: Yang, Jason
Published: (2024)

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

Equations over Finite Monoids with Infinite Promises
by: Larrauri, Alberto, et al.
Published: (2025)

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

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
by: Wang, Chengu
Published: (2026)

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
by: Rai, Shanthanu S
Published: (2024)

Lower Bounds against the Ideal Proof System in Finite Fields
by: Elbaz, Tal, et al.
Published: (2025)

Optimal Inapproximability of Generalized Linear Equations over a Finite Group
by: Bhangale, Amey, et al.
Published: (2026)

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

New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality
by: Nagy, Tomáš, et al.
Published: (2025)

Optimal Inapproximability of Promise Equations over Finite Groups
by: Butti, Silvia, et al.
Published: (2024)

Low-Rank Matrix Approximation for Neural Network Compression
by: Cherukuri, Kalyan, et al.
Published: (2025)

New Hardness Results for Low-Rank Matrix Completion
by: Chawin, Dror, et al.
Published: (2025)

Solving Polynomial Equations Over Finite Fields
by: Dell, Holger, et al.
Published: (2024)

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

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

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

Optimal Scheduling of Graph States via Path Decompositions
by: Elman, Samuel J., et al.
Published: (2024)

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

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

Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields
by: Dwivedi, Ashish, et al.
Published: (2024)

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

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2022)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
by: Li, Tiange, et al.
Published: (2026)

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

Lossless Model Compression via Joint Low-Rank Factorization Optimization
by: Zhang, Boyang, et al.
Published: (2024)

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

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

Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
by: Hair, Isaac M, et al.
Published: (2026)

Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
by: Hu, Jerry Yao-Chieh, et al.
Published: (2024)

Improved Debordering of Waring Rank
by: Shpilka, Amir
Published: (2025)

Tensor Hinted Mv Conjectures
by: Song, Zhao
Published: (2026)

Solving 4-Block Integer Linear Programs Faster Using Affine Decompositions of the Right-Hand Sides
by: Lassota, Alexandra, et al.
Published: (2026)

Tensor Spectral Threshold is $\exists\mathbb{R}$-Hard
by: Majumdar, Angshul
Published: (2026)