Cover Image

New Perspectives on Semiring Applications to Dynamic Programming

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Baril, Ambroise, Couceiro, Miguel, Lagerkvist, Victor
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Rings and Algebras
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
by: Baril, Ambroise, et al.
Published: (2025)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
by: Baril, Ambroise, et al.
Published: (2024)

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

The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
by: Bodirsky, Manuel, et al.
Published: (2025)

A quasi-optimal lower bound for skew polynomial multiplication
by: Chen, Qiyuan, et al.
Published: (2024)

Efficient Compression in Semigroups
by: Thumm, Alexander, et al.
Published: (2026)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
by: Zhuk, Dmitriy
Published: (2024)

Symmetric Linear Arc Monadic Datalog and Gadget Reductions
by: Bodirsky, Manuel, et al.
Published: (2024)

Graph Homomorphisms and Universal Algebra
by: Bodirsky, Manuel
Published: (2026)

The complexity of finding coset-generating polymorphisms and the promise metaproblem
by: Bodirsky, Manuel, et al.
Published: (2026)

On the uniqueness and computation of commuting extensions
by: Koiran, Pascal
Published: (2024)

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
by: Feller, Roman, et al.
Published: (2024)

Network Satisfaction Problems Solved by k-Consistency
by: Bodirsky, Manuel, et al.
Published: (2023)

Stability of Boolean function classes with respect to clones of linear functions
by: Couceiro, Miguel, et al.
Published: (2021)

Semirings generated by idempotents
by: Dolžan, David
Published: (2024)

Non-commutative linear algebra and plurisubharmonic functions of quaternionic variables
by: Alesker, Semyon
Published: (2001)

On the complexity of solving equations over the symmetric group $S_4$
by: Aichinger, Erhard, et al.
Published: (2025)

Multipoint Schwarz-Pick Lemma for the quaternionic case
by: Bisi, Cinzia, et al.
Published: (2023)

New Approaches to Complexity via Quantum Graphs
by: Culf, Eric, et al.
Published: (2023)

On the Asymptotic Nonnegative Rank of Matrices and its Applications in Information Theory
by: Chee, Yeow Meng, et al.
Published: (2023)

Semiring arising as Lattice of Groupsemirings
by: Rajan, A. R., et al.
Published: (2024)

Tensor decomposition beyond uniqueness, with an application to the minrank problem
by: Koiran, Pascal, et al.
Published: (2025)

Flat Semimodules & von Neumann Regular Semirings
by: Abuhlail, Jawad, et al.
Published: (2019)

CSPs with Few Alien Constraints
by: Jonsson, Peter, et al.
Published: (2024)

Debordering Closure Results in Determinantal and Pfaffian Ideals
by: Dey, Anakin, et al.
Published: (2025)

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

Invariants and Automorphisms for slice regular functions
by: Bisi, Cinzia, et al.
Published: (2024)

Isotropy and completeness indices of multilinear maps
by: Chen, Qiyuan, et al.
Published: (2025)

A base change framework for tensor functions
by: Chen, Qiyuan
Published: (2026)

Learning Read-Once Determinants and the Principal Minor Assignment Problem
by: Aravind, Abhiram, et al.
Published: (2026)

On the Subtractive Ideal Structure of Commutative Semirings
by: Sengupta, Pubali, et al.
Published: (2026)

The Interval $[\mathsf{V}(S_7),\mathsf{V}(B_2^1)]$ of Semiring Varieties Has the Cardinality of the Continuum
by: Gao, Zidong, et al.
Published: (2026)

A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
by: Lagerkvist, Victor, et al.
Published: (2025)

Fueter trees for Dunkl-regular functions over alternative *-algebras
by: Perotti, Alessandro
Published: (2026)

A New Perspective on Eigenvalues and Eigenvectors of Bicomplex Linear Operators
by: Anjali, Anjali, et al.
Published: (2025)

Existence and nonexistence of commutativity gadgets for entangled CSPs
by: Culf, Eric, et al.
Published: (2025)

Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete
by: Hutton, Kiera, et al.
Published: (2025)

Gap-preserving reductions and RE-completeness of independent set games
by: Mančinska, Laura, et al.
Published: (2025)

MIPco=coRE
by: Lin, Junqiao
Published: (2025)

Explicit optimal-length locally repairable codes of distance 5
by: Beemer, Allison, et al.
Published: (2018)