:: Library Catalog

Cover Image

Saved in:

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

Similar Items

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

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

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

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

Permanents of random matrices over finite fields
by: Hunter, Zach, et al.
Published: (2026)

Recovering polynomials over finite fields from noisy character values
by: Kopparty, Swastik
Published: (2026)

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

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

Minimum cost flow decomposition on arc-coloured networks
by: Neto, Claudio Carvalho, et al.
Published: (2025)

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

Sketching approximability of all finite CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

Tractability results for integration in subspaces of the Wiener algebra
by: Dick, Josef, et al.
Published: (2024)

Some structural complexity results for $\exists\mathbb R$
by: Meer, Klaus, et al.
Published: (2025)

Closure under factorization from a result of Furstenberg
by: Bhattacharjee, Somnath, et al.
Published: (2025)

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
by: Chen, Lijie, et al.
Published: (2025)

Holomorphic maps sharing preimages over finitely generated fields
by: Pakovich, Fedor
Published: (2025)

Nonuniform Deterministic Finite Automata over finite algebraic structures
by: Idziak, Paweł M., et al.
Published: (2025)

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

Consistent Query Answering over SHACL Constraints
by: Ahmetaj, Shqiponja, et al.
Published: (2024)

Log canonical thresholds at infinity
by: Bivià-Ausina, Carles, et al.
Published: (2026)

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

Local Correction of Linear Functions over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

A linear bound for the size of the finite terminal assembly of a directed non-cooperative tile assembly system
by: Ivanov, Sergiu, et al.
Published: (2024)

Constant-depth circuits for polynomial GCD over any characteristic
by: Bhattacharjee, Somnath, et al.
Published: (2025)

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

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
by: Komarath, Balagopal, et al.
Published: (2026)

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

New Direct Sum Tests
by: Westover, Alek, et al.
Published: (2024)

Hardness results for decoding the surface code with Pauli noise
by: Fischer, Alex, et al.
Published: (2023)

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
by: Byramji, Farzan, et al.
Published: (2025)

Circuits and Formulas for Datalog over Semirings
by: Fan, Austen Z., et al.
Published: (2025)

Estimates for the $\bar{\partial}$-equation on canonical surfaces
by: Andersson, Mats, et al.
Published: (2018)

Temporal Cycle Detection and Acyclic Temporization
by: de Andrade, Davi, et al.
Published: (2025)

New Pseudorandom Generators and Correlation Bounds Using Extractors
by: Kumar, Vinayak M.
Published: (2025)

New Techniques for Constructing Rare-Case Hard Functions
by: Nareddy, Tejas, et al.
Published: (2024)

Inconsistency Probability of Sparse Equations over F2
by: Horak, P., et al.
Published: (2026)

Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs
by: Casteigts, Arnaud, et al.
Published: (2024)

Representing Matroids over the Reals is $\exists \mathbb R$-complete
by: Kim, Eun Jung, et al.
Published: (2023)

Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable
by: Mouli, Sasank
Published: (2024)

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)