Image de couverture de livre

PosSLP and Sum of Squares

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Bläser, Markus, Dörfler, Julian, Jindal, Gorav
Format:	Preprint
Publié:	2024
Sujets:	Computational Complexity Discrete Mathematics F.1.3; G.2.0; F.2.1
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
par: Bläser, Markus, et autres
Publié: (2025)

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

Symmetric Arithmetic Circuits
par: Dawar, Anuj, et autres
Publié: (2020)

Lower Bounds for Symmetric Circuits for the Determinant
par: Dawar, Anuj, et autres
Publié: (2021)

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

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
par: Burke, Kyle, et autres
Publié: (2025)

An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands
par: Shalaby, Ahmed, et autres
Publié: (2024)

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
par: Anand, Emile
Publié: (2025)

Which graph motif parameters count?
par: Bläser, Markus, et autres
Publié: (2025)

On the Complexity of Problems on Graphs Defined on Groups
par: Das, Bireswar, et autres
Publié: (2025)

Algorithmic hardness of the partition function for nucleic acid strands
par: Ducloz, Gwendal, et autres
Publié: (2025)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
par: Anand, Emile, et autres
Publié: (2024)

Beyond Worst-Case Subset Sum: An Adaptive, Structure-Aware Solver with Sub-$2^{n/2}$ Enumeration
par: Salas, Jesus
Publié: (2025)

Graph-Based Deterministic Polynomial Framwork for NP Problems
par: Lee, Changryeol
Publié: (2025)

Nonuniform Deterministic Finite Automata over finite algebraic structures
par: Idziak, Paweł M., et autres
Publié: (2025)

Constructibility and the P versus NP problem
par: Hole, Arne
Publié: (2024)

On Sampling Lower Bounds for Polynomials
par: Khodabandeh, Mohammad Mahdi, et autres
Publié: (2026)

On the Counting Complexity of the Skolem Problem
par: Jindal, Gorav, et autres
Publié: (2024)

Skolem Meets Bateman-Horn
par: Luca, Florian, et autres
Publié: (2023)

On the Orthogonality of Generalized Pattern Sequences
par: Li, Shuo
Publié: (2024)

Col is PSPACE-complete on Triangular Grids
par: Burke, Kyle, et autres
Publié: (2025)

Polymer Dynamics via Cliques: New Conditions for Approximations
par: Friedrich, Tobias, et autres
Publié: (2020)

Summa Summarum: Moessner's Theorem without Dynamic Programming
par: Danvy, Olivier
Publié: (2024)

Small Shadow Partitions
par: Kopparty, Swastik, et autres
Publié: (2024)

Reducing Matroid Optimization to Basis Search
par: Streit, Robert, et autres
Publié: (2024)

Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
par: Chauhan, Archit, et autres
Publié: (2026)

Slow Convergence of Ising and Spin Glass Models with Well-Separated Frustrated Vertices
par: Gillman, David, et autres
Publié: (2026)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
par: Lela, Marko
Publié: (2025)

A Permutation Avoidance Game with Reverse Replies and Monotone Traps
par: Ulfarsson, Henning
Publié: (2026)

Optimal covering of rectangular grid graphs with tours of constrained length
par: Bereg, Sergey, et autres
Publié: (2025)

Notes on CSPs and Polymorphisms
par: Brady, Zarathustra
Publié: (2022)

Quantitative Edge Eigenvector Universality for Random Regular Graphs: Berry-Esseen Bounds with Explicit Constants
par: Nagel, Leonhard
Publié: (2025)

Construction of Minkowski Sums by Cellular Automata
par: Tahay, Pierre-Adrien
Publié: (2024)

New Results on Edge-coloring and Total-coloring of Split Graphs
par: Couto, Fernanda, et autres
Publié: (2023)

Fair Division Among Couples and Small Groups
par: Gölz, Paul, et autres
Publié: (2025)

A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
par: Burke, Kyle, et autres
Publié: (2024)

I/O complexity and pebble games with partial computations
par: Sobczyk, Aleksandros
Publié: (2024)

Efficient Approximation of Fractional Hypertree Width
par: Korchemna, Viktoriia, et autres
Publié: (2024)

Preliminaries on the Accurate Estimation of the Hurst Exponent Using Time Series
par: Millán, Ginno, et autres
Publié: (2021)

Polynomial Complexity of Inversion of sequences and Local Inversion of Maps
par: Sule, Virendra
Publié: (2024)