Copertina

Does Subset Sum Admit Short Proofs?

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Włodarczyk, Michał
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Subset Balancing and Generalized Subset Sum via Lattices
di: Gao, Yiming, et al.
Pubblicazione: (2026)

Improved Space Bounds for Subset Sum
di: Belova, Tatiana, et al.
Pubblicazione: (2024)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
di: Sajith, Thejas Radhika
Pubblicazione: (2025)

On the Parameterized Complexity of Min-Sum-Radii
di: Kumar, Pankaj, et al.
Pubblicazione: (2026)

Streaming Zero-Knowledge Proofs
di: Cormode, Graham, et al.
Pubblicazione: (2023)

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

A Simple Proof that Ricochet Robots is PSPACE-Complete
di: Balanza-Martinez, Jose, et al.
Pubblicazione: (2024)

Precoloring extension with demands on paths
di: Das, Arun Kumar, et al.
Pubblicazione: (2025)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
di: Foucaud, Florent, et al.
Pubblicazione: (2023)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
di: Salas, Jesus
Pubblicazione: (2025)

Exact Algorithms for Distance to Unique Vertex Cover
di: Fioravantes, Foivos, et al.
Pubblicazione: (2025)

Frontier Space-Time Algorithms Using Only Full Memory
di: Chmel, Petr, et al.
Pubblicazione: (2026)

Dequantization and Hardness of Spectral Sum Estimation
di: Edenhofer, Roman, et al.
Pubblicazione: (2025)

On the Power of Interactive Proofs for Learning
di: Gur, Tom, et al.
Pubblicazione: (2024)

Computing Subset Vertex Covers in $H$-Free Graphs
di: Brettell, Nick, et al.
Pubblicazione: (2023)

Fast and simple multiplication of bounded twin-width matrices
di: Kozma, László, et al.
Pubblicazione: (2026)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
di: Hirahara, Shuichi, et al.
Pubblicazione: (2023)

Dequantizing Short-Path Quantum Algorithms
di: Gall, François Le, et al.
Pubblicazione: (2026)

Can You Link Up With Treewidth?
di: Curticapean, Radu, et al.
Pubblicazione: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
di: Wang, Yichuan
Pubblicazione: (2024)

Simple approximation algorithms for Polyamorous Scheduling
di: Biktairov, Yuriy, et al.
Pubblicazione: (2024)

Size Minimization For Multi-Output AND-Functions
di: Armbruster, Susanne
Pubblicazione: (2024)

TSP Escapes the $O(2^n n^2)$ Curse
di: Stoian, Mihail
Pubblicazione: (2024)

Cluster Editing on Cographs and Related Classes
di: Lafond, Manuel, et al.
Pubblicazione: (2024)

Improved Hardness-of-Approximation for Token Swapping
di: Hiken, Sam, et al.
Pubblicazione: (2024)

Near-Optimal Averaging Samplers and Matrix Samplers
di: Xun, Zhiyang, et al.
Pubblicazione: (2024)

On the complexity and approximability of Bounded access Lempel Ziv coding
di: Cicalese, Ferdinando, et al.
Pubblicazione: (2024)

Parameterized Vertex Integrity Revisited
di: Hanaka, Tesshu, et al.
Pubblicazione: (2024)

On approximability of the Permanent of PSD matrices
di: Ebrahimnejad, Farzam, et al.
Pubblicazione: (2024)

Further Explanations on "SAT Requires Exhaustive Search"
di: Dong, Qingxiu, et al.
Pubblicazione: (2024)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
di: Sato, Atsuki, et al.
Pubblicazione: (2024)

Randomized query composition and product distributions
di: Sanyal, Swagato
Pubblicazione: (2024)

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
di: Heeger, Klaus, et al.
Pubblicazione: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
di: Stoian, Mihail
Pubblicazione: (2024)

On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
di: Kuschner, Jordan, et al.
Pubblicazione: (2024)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
di: Yang, Yang
Pubblicazione: (2024)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
di: Kumar, Mrinal, et al.
Pubblicazione: (2024)

Solving Polynomial Equations Over Finite Fields
di: Dell, Holger, et al.
Pubblicazione: (2024)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
di: Bentert, Matthias, et al.
Pubblicazione: (2024)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
di: Chakraborty, Dibyayan, et al.
Pubblicazione: (2024)