Image de couverture de livre

Certificate-Sensitive Subset Sum: Realizing Instance Complexity

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Salas, Jesus
Format:	Preprint
Publié:	2025
Sujets:	Computational Complexity Data Structures and Algorithms F.1.3; F.2.2
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
par: Saha, Barna, 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)

Line Cover and Related Problems
par: Bentert, Matthias, et autres
Publié: (2025)

Realizing temporal graphs from fastest travel times
par: Klobas, Nina, et autres
Publié: (2023)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
par: Krithika, R., et autres
Publié: (2023)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
par: Kowaluk, Miroslaw, et autres
Publié: (2025)

Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM
par: Randolph, Tim, et autres
Publié: (2024)

Min-CSPs on Complete Instances
par: Anand, Aditya, et autres
Publié: (2024)

Identity Testing for Circuits with Exponentiation Gates
par: Li, Jiatu, et autres
Publié: (2025)

Towards universally optimal sorting algorithms
par: Sen, Sandeep
Publié: (2025)

Spanning Trees Minimizing Branching Costs
par: Gargano, Luisa, et autres
Publié: (2024)

An Algorithm for a Variation of the Shortest Common Superstring Problem
par: Gilfanov, Arthur
Publié: (2024)

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
par: Sarriguren, Alfredo Goñi
Publié: (2024)

Beating Meet-in-the-Middle for Subset Balancing Problems
par: Randolph, Tim, et autres
Publié: (2025)

When Votes Change and Committees Should (Not)
par: Bredereck, Robert, et autres
Publié: (2020)

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
par: Lingas, Andrzej
Publié: (2026)

Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses
par: Chen, Lin, et autres
Publié: (2025)

On the Complexity of Determinations
par: Hellerstein, Joseph M.
Publié: (2026)

Approximation Schemes for k-Subset Sum Ratio and k-way Number Partitioning Ratio
par: Kanellopoulos, Sotiris, et autres
Publié: (2025)

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

Graph Threading with Turn Costs
par: Demaine, Erik D., et autres
Publié: (2024)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
par: Dvořák, Pavel, et autres
Publié: (2017)

A Piecewise Approach for the Analysis of Exact Algorithms
par: Clinch, Katie, et autres
Publié: (2024)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
par: Grochow, Joshua A., et autres
Publié: (2025)

On the Complexity of Neural Computation in Superposition
par: Adler, Micah, et autres
Publié: (2024)

An Efficient Algorithm for Unbalanced 1D Transportation
par: Gouvine, Gabriel
Publié: (2023)

A Decomposition Approach to the Weighted $k$-server Problem
par: Ayyadevara, Nikhil, et autres
Publié: (2024)

Eliminating Illusion in Directed Networks
par: Jana, Sougata, et autres
Publié: (2026)

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
par: Fairbairn, David L., et autres
Publié: (2024)

Minimum Riesz s-Energy Subset Selection in Ordered Point Sets via Dynamic Programming
par: Emmerich, Michael
Publié: (2025)

Complexity of Finding and Enumerating Interconnection Trees
par: Demange, Noé, et autres
Publié: (2026)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
par: Jansen, Klaus, et autres
Publié: (2024)

On the Length of Strongly Monotone Descending Chains over $\mathbb{N}^d$
par: Schmitz, Sylvain, et autres
Publié: (2023)

Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes
par: Chauhan, Archit, et autres
Publié: (2025)

Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision
par: Koiran, Pascal, et autres
Publié: (2022)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
par: Conneryd, Jonas, et autres
Publié: (2025)

On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting
par: Goswami, Mayank, et autres
Publié: (2022)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
par: DeHaan, Ian, et autres
Publié: (2024)

Large cliques and large independent sets: can they coexist?
par: Feige, Uriel, et autres
Publié: (2025)

Bidirectional Dijkstra's Algorithm is Instance-Optimal
par: Haeupler, Bernhard, et autres
Publié: (2024)