Cover Image

Algorithmic hardness of the partition function for nucleic acid strands

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ducloz, Gwendal, Shalaby, Ahmed, Woods, Damien
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity F.2; F.1.3; G.2.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands
by: Shalaby, Ahmed, et al.
Published: (2024)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
by: Anand, Emile, et al.
Published: (2024)

On Sampling Lower Bounds for Polynomials
by: Khodabandeh, Mohammad Mahdi, et al.
Published: (2026)

PosSLP and Sum of Squares
by: Bläser, Markus, et al.
Published: (2024)

Col is PSPACE-complete on Triangular Grids
by: Burke, Kyle, et al.
Published: (2025)

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
by: Pavlov, Gorgi
Published: (2026)

Symmetric Arithmetic Circuits
by: Dawar, Anuj, et al.
Published: (2020)

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
by: Burke, Kyle, et al.
Published: (2025)

Dichotomy for orderings?
by: Kun, Gábor, et al.
Published: (2025)

On the Complexity of Determinations
by: Hellerstein, Joseph M.
Published: (2026)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
by: Antonelli, Melissa, et al.
Published: (2025)

Which graph motif parameters count?
by: Bläser, Markus, et al.
Published: (2025)

Faster Algorithms for Structured Matrix Multiplication via Flip Graph Search
by: Khoruzhii, Kirill, et al.
Published: (2025)

Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
by: Bläser, Markus, et al.
Published: (2025)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
by: Conneryd, Jonas, et al.
Published: (2025)

On bounded depth proofs for Tseitin formulas on the grid; revisited
by: Håstad, Johan, et al.
Published: (2022)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
by: de Rezende, Susanna F., et al.
Published: (2026)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
by: de Rezende, Susanna F., et al.
Published: (2024)

Supercritical Tradeoffs for Monotone Circuits
by: Göös, Mika, et al.
Published: (2024)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
by: Conneryd, Jonas, et al.
Published: (2025)

A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
by: Burke, Kyle, et al.
Published: (2024)

Graph-Based Deterministic Polynomial Framwork for NP Problems
by: Lee, Changryeol
Published: (2025)

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

Imperative process algebra and models of computation
by: Middelburg, C. A.
Published: (2022)

Reduction of the graph isomorphism problem to equality checking of $n$-variables polynomials and the algorithms that use the reduction
by: Prolubnikov, Alexander
Published: (2015)

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

NP-hardness of p-adic linear regression
by: Baker, Gregory D.
Published: (2026)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
by: de Rezende, Susanna F., et al.
Published: (2019)

Small Shadow Partitions
by: Kopparty, Swastik, et al.
Published: (2024)

On the Satisfaction Probabilities of $k$-CNF Formulas
by: Tantau, Till
Published: (2022)

Arithmetic Complexity of Solutions of the Dirichlet Problem
by: Boche, Holger, et al.
Published: (2026)

On the Complexity of Problems on Graphs Defined on Groups
by: Das, Bireswar, et al.
Published: (2025)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
by: Salas, Jesus
Published: (2025)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
by: Saha, Barna, et al.
Published: (2024)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by: Kumar, Mrinal, et al.
Published: (2018)

Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections
by: Eberly, Wayne, et al.
Published: (2007)

Certification of the QR factor R, and of lattice basis reducedness
by: Villard, Gilles
Published: (2007)

Polynomial-time Tractable Problems over the $p$-adic Numbers
by: Fehm, Arno, et al.
Published: (2025)