Cover Image

The Greedy Coin Change Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gupta, Shreya, Huang, Boyang, Impagliazzo, Russell
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Computational Complexity of Factored Graphs
by: Gupta, Shreya, et al.
Published: (2024)

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
by: Byramji, Farzan, et al.
Published: (2025)

High Rate Efficient Local List Decoding from HDX
by: Dikstein, Yotam, et al.
Published: (2026)

Subquadratic Algorithms and Hardness for Attention with Any Temperature
by: Gupta, Shreya, et al.
Published: (2025)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
by: Aaronson, Scott, et al.
Published: (2023)

Replicability in High Dimensional Statistics
by: Hopkins, Max, et al.
Published: (2024)

Submodular Maximization under Supermodular Constraint: Greedy Guarantees
by: Srivastava, Ajitesh, et al.
Published: (2026)

On Computability of Computable Problems
by: Khaliq, Asad
Published: (2023)

The Stochastic Arrival Problem
by: Webster, Thomas
Published: (2022)

On the Hardness of the Drone Delivery Problem
by: Bartlmae, Simon, et al.
Published: (2025)

Continuous Defensive Domination Problems
by: Grüne, Christoph, et al.
Published: (2026)

Parameterized Complexity of the Star Decomposition Problem
by: Hajebi, Sahab, et al.
Published: (2024)

On the Exact Matching Problem in Dense Graphs
by: Maalouly, Nicolas El, et al.
Published: (2024)

On the Complexity of Problems on Tree-structured Graphs
by: Bodlaender, Hans L., et al.
Published: (2022)

Reductions Between Code Equivalence Problems
by: Cheraghchi, Mahdi, et al.
Published: (2025)

Total Search Problems in $\mathsf{ZPP}$
by: Fleming, Noah, et al.
Published: (2025)

The 2-Attractor Problem is NP-Complete
by: Fuchs, Janosch, et al.
Published: (2023)

Inverse Intersections for Boolean Satisfiability Problems
by: Homer, Paul W.
Published: (2025)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2022)

No Complete Problem for Constant-Cost Randomized Communication
by: Fang, Yuting, et al.
Published: (2024)

P-time Algorithms for Typical #EO Problems
by: Meng, Boning, et al.
Published: (2024)

Trading Determinism for Time: The k-Reach Problem
by: Bhadra, Ronak, et al.
Published: (2024)

The Line Traveling Salesman and Repairman Problem with Collaboration
by: Golak, Julian, et al.
Published: (2025)

Maximum Matching and Related Problems in Catalytic Logspace
by: Chakraborty, Srijan, et al.
Published: (2026)

Strong Inapproximability for a Promise Rank Problem
by: Guruswami, Venkatesan, et al.
Published: (2026)

Explaining the Ubiquity of Phase Transitions in Decision Problems
by: Jackson, Andrew
Published: (2025)

An Efficient Algorithm for Solving the 2-MAXSAT Problem
by: Chen, Yangjun
Published: (2023)

Geometry Of The Subset Sum Problem -- Part I
by: Bollepalli, Srinivas Balaji
Published: (2025)

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
by: Gupta, Rishav, et al.
Published: (2026)

On the Principal Minor Expansion and Complexity of the Symmetrized Determinant
by: Agarwal, Sanyam, et al.
Published: (2026)

Complexity Thresholds for the Constrained Colored Token Swapping Problem
by: Bilò, Davide, et al.
Published: (2026)

Feedback Set Problems on Bounded-Degree (Planar) Graphs
by: Bai, Tian, et al.
Published: (2026)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
by: Cavalar, Bruno P., et al.
Published: (2025)

Complexity Theory for Quantum Promise Problems
by: Chia, Nai-Hui, et al.
Published: (2024)

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
by: Lichter, Moritz, et al.
Published: (2024)

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
by: Yung, Kingsley
Published: (2024)

Partial Minimum Branching Program Size Problem is ETH-hard
by: Glinskih, Ludmila, et al.
Published: (2024)

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
by: Fu, Cheng-Hao, et al.
Published: (2025)

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
by: Jackson, Andrew
Published: (2025)

The First Known Problem That Is FPT with Respect to Node Scanwidth but Not Treewidth
by: Schestag, Jannik, et al.
Published: (2026)