Cover Image

Ruling Out Low-rank Matrix Multiplication Tensor Decompositions with Symmetries via SAT

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Yang, Jason
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Low-Rank Tensor 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)

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

When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames
by: Krebs, Andreas, et al.
Published: (2025)

Improving the Leading Constant of Matrix Multiplication
by: Alman, Josh, et al.
Published: (2024)

On Matrix Multiplication and Polynomial Identity Testing
by: Andrews, Robert
Published: (2022)

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

An Intrinsic Barrier for Resolving P = NP (2-SAT as Flat, 3-SAT as High-Dimensional Void-Rich)
by: Alasli, M.
Published: (2025)

A Reply to "On Salum's Algorithm for X3SAT"
by: Salum, Latif
Published: (2021)

Linear Planar 3-SAT and Its Applications in Planning
by: Desbois, Victorien, et al.
Published: (2025)

An even simpler hard variant of Not-All-Equal 3-SAT
by: Darmann, Andreas, et al.
Published: (2024)

A Graphical #SAT Algorithm for Formulae with Small Clause Density
by: Laakkonen, Tuomas, et al.
Published: (2022)

Complex to Rational Fast Matrix Multiplication
by: Moran, Yoav, et al.
Published: (2026)

Matrix Multiplication in the MPC Model
by: Joshi, Lakshya, et al.
Published: (2025)

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

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

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

Approximately counting maximal independent set is equivalent to #SAT
by: Zhang, Hao, et al.
Published: (2024)

Persistent (Co)Homology in Matrix Multiplication Time
by: Morozov, Dmitriy, et al.
Published: (2024)

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
by: Krokhin, Andrei, et al.
Published: (2025)

A Hypergraph Container Method on Spread SAT: Approximation and Speedup
by: Han, Zicheng, et al.
Published: (2026)

On the Mysteries of MAX NAE-SAT
by: Brakensiek, Joshua, et al.
Published: (2020)

Quantum k-SAT Related Hypergraph Problems
by: Kremer, Simon-Luca, et al.
Published: (2025)

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

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

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

On the Chow-rank of the permanent
by: Xu, Rongyu, et al.
Published: (2023)

Fast Matrix Multiplication meets the Submodular Width
by: Abo-Khamis, Mahmoud, et al.
Published: (2024)

More Asymmetry Yields Faster Matrix Multiplication
by: Alman, Josh, et al.
Published: (2024)

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

A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization
by: Schreiber, Franz J., et al.
Published: (2025)

Optimal Scheduling of Graph States via Path Decompositions
by: Elman, Samuel J., 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)

BusOut is NP-complete
by: Ishibashi, Takehiro, et al.
Published: (2025)

Further Explanations on "SAT Requires Exhaustive Search"
by: Dong, Qingxiu, et al.
Published: (2024)

A Polynomial Time Algorithm for 3SAT
by: Quigley, Robert
Published: (2024)

Geometric Interpretation of 3-SAT and Phase Transition
by: Gillet, Frederic
Published: (2025)

A Note On The Natural Range Of Unambiguous-SAT
by: Pay, Tayfun
Published: (2023)

Refuting approaches to the log-rank conjecture for XOR functions
by: Hatami, Hamed, et al.
Published: (2023)