On the public citation graph

SETH-based Lower Bounds for Subset Sum and Bicriteria Path

0 signed · 111 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/nav.3800250314openalex-snapshot
The constrained shortest path problem
inferredcites →https://doi.org/10.1002/rsa.10068openalex-snapshot
Simple analysis of graph tests for linearity and PCP
inferredcites →https://doi.org/10.1006/jcss.2000.1727openalex-snapshot
On the Complexity of k-SAT
inferredcites →https://doi.org/10.1006/jcss.2001.1774openalex-snapshot
Which Problems Have Strongly Exponential Complexity?
inferredcites →https://doi.org/10.1007/978-1-4684-2001-2_9openalex-snapshot
Reducibility among Combinatorial Problems
inferredcites →https://doi.org/10.1007/978-3-319-06089-7_7openalex-snapshot
The Parameterized Complexity of Domination-Type Problems and Application to Linear Codes
inferredcites →https://doi.org/10.1007/978-3-319-21275-3_14openalex-snapshot
Lower Bounds Based on the Exponential-Time Hypothesis
inferredcites →https://doi.org/10.1007/978-3-319-62127-2_9openalex-snapshot
Dynamic Graph Coloring
inferredcites →https://doi.org/10.1007/978-3-540-24777-7openalex-snapshot
Knapsack Problems
inferredcites →https://doi.org/10.1007/978-3-642-11269-0_6openalex-snapshot
The Complexity of Satisfiability of Small Depth Circuits
inferredcites →https://doi.org/10.1007/978-3-642-13190-5_12openalex-snapshot
New Generic Algorithms for Hard Knapsacks
inferredcites →https://doi.org/10.1007/978-3-642-32009-5_42openalex-snapshot
Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
inferredcites →https://doi.org/10.1007/978-3-642-32589-2_62openalex-snapshot
Reducing a Target Interval to a Few Exact Queries
inferredcites →https://doi.org/10.1007/978-3-642-39206-1_1openalex-snapshot
Exact Weight Subgraphs and the k-Sum Conjecture
inferredcites →https://doi.org/10.1007/978-3-642-39206-1_5openalex-snapshot
Space–Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm
inferredcites →https://doi.org/10.1007/978-3-642-48782-8_9openalex-snapshot
Bicriterion Path Problems
inferredcites →https://doi.org/10.1007/978-3-642-55753-8_52openalex-snapshot
Computer Aided Scheduling of Switching Engines
inferredcites →https://doi.org/10.1007/978-3-662-43948-7_10openalex-snapshot
On Hardness of Jumbled Indexing
inferredcites →https://doi.org/10.1007/978-3-662-43948-7_4openalex-snapshot
Consequences of Faster Alignment of Sequences
inferredcites →https://doi.org/10.1007/978-3-662-44777-2_1openalex-snapshot
Losing Weight by Gaining Edges
inferredcites →https://doi.org/10.1007/978-3-662-44777-2_67openalex-snapshot
Space-Efficient Randomized Algorithms for K-SUM
inferredcites →https://doi.org/10.1007/978-3-662-47672-7_61openalex-snapshot
Local Reductions
inferredcites →https://doi.org/10.1007/bf00189260openalex-snapshot
Efficient cryptographic schemes provably as secure as subset sum
inferredcites →https://doi.org/10.1007/s00224-014-9550-zopenalex-snapshot
Hardness of Approximation for Knapsack Problems
inferredcites →https://doi.org/10.1007/s00453-002-0989-yopenalex-snapshot
Dynamic Programming on the Word RAM
inferredcites →https://doi.org/10.1007/s00453-006-0191-8openalex-snapshot
Real-Time Scheduling with a Budget
inferredcites →https://doi.org/10.1007/s00453-007-9036-3openalex-snapshot
Subquadratic Algorithms for 3SUM
inferredcites →https://doi.org/10.1007/s00453-014-9946-9openalex-snapshot
$$\mathrm {3SUM}$$ 3 SUM , $$\mathrm {3XOR}$$ 3 XOR , Triangles
inferredcites →https://doi.org/10.1007/s00453-015-0079-6openalex-snapshot
Improved Subquadratic 3SUM
inferredcites →https://doi.org/10.1007/s00493-014-3078-3openalex-snapshot
The communication complexity of addition
inferredcites →https://doi.org/10.1016/0022-247x(66)90020-5openalex-snapshot
The shortest route problem with constraints
inferredcites →https://doi.org/10.1016/0925-7721(95)00022-2openalex-snapshot
On a class of O(n2) problems in computational geometry
inferredcites →https://doi.org/10.1016/j.comnet.2010.05.017openalex-snapshot
A survey on multi-constrained optimal path computation: Exact and approximate algorithms
inferredcites →https://doi.org/10.1016/j.cor.2004.03.002openalex-snapshot
Where are the hard knapsack problems?
inferredcites →https://doi.org/10.1016/j.cor.2008.02.002openalex-snapshot
A comparison of solution strategies for biobjective shortest path problems
inferredcites →https://doi.org/10.1016/j.dam.2007.03.023openalex-snapshot
Open problems around exact algorithms
inferredcites →https://doi.org/10.1016/j.ejor.2010.05.036openalex-snapshot
Complexity of single machine scheduling subject to nonnegative inventory constraints
inferredcites →https://doi.org/10.1016/j.ipl.2009.04.018openalex-snapshot
Approximation algorithms for multi-agent scheduling to minimize total weighted completion time
inferredcites →https://doi.org/10.1016/j.ipl.2016.09.002openalex-snapshot
A short note on Merlin–Arthur protocols for subset sum
inferredcites →https://doi.org/10.1016/j.jcss.2012.04.004openalex-snapshot
Bin packing with fixed number of bins revisited
inferredcites →https://doi.org/10.1016/j.omega.2013.07.001openalex-snapshot
A combined robot selection and scheduling problem for flow-shops with no-wait restrictions
inferredcites →https://doi.org/10.1016/j.tcs.2005.09.023openalex-snapshot
A new algorithm for optimal 2-constraint satisfaction and its implications
inferredcites →https://doi.org/10.1016/s0020-0190(02)00205-3openalex-snapshot
An improved FPTAS for Restricted Shortest Path
inferredcites →https://doi.org/10.1016/s0167-6377(01)00069-4openalex-snapshot
A simple efficient approximation scheme for the restricted shortest path problem
inferredcites →https://doi.org/10.1016/s0747-7171(08)80013-2openalex-snapshot
Matrix multiplication via arithmetic progressions
inferredcites →https://doi.org/10.1073/pnas.32.12.331openalex-snapshot
On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
inferredcites →https://doi.org/10.1090/psapm/042/1095552openalex-snapshot
The rise and fall of knapsack cryptosystems
inferredcites →https://doi.org/10.1109/18.21214openalex-snapshot
A knapsack-type public key cryptosystem based on arithmetic in finite fields
inferredcites →https://doi.org/10.1109/5.4443openalex-snapshot
Cryptanalysis: a survey of recent results
inferredcites →https://doi.org/10.1109/90.748088openalex-snapshot
QoS routing in networks with uncertain parameters
inferredcites →https://doi.org/10.1109/ccc.2006.6openalex-snapshot
A Duality between Clause Width and Clause Density for SAT
inferredcites →https://doi.org/10.1109/comst.2003.5342226openalex-snapshot
Constraint-based routing in the internet: Basic principles and recent research
inferredcites →https://doi.org/10.1109/focs.2014.53openalex-snapshot
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems
inferredcites →https://doi.org/10.1109/focs.2014.72openalex-snapshot
Threesomes, Degenerates, and Love Triangles
inferredcites →https://doi.org/10.1109/focs.2014.76openalex-snapshot
Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails
inferredcites →https://doi.org/10.1109/focs.2015.14openalex-snapshot
Tight Hardness Results for LCS and Other Sequence Similarity Measures
inferredcites →https://doi.org/10.1109/focs.2015.15openalex-snapshot
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
inferredcites →https://doi.org/10.1109/focs.2016.56openalex-snapshot
Which Regular Expression Patterns Are Hard to Match?
inferredcites →https://doi.org/10.1109/focs.2017.11openalex-snapshot
On the Quantitative Hardness of CVP
inferredcites →https://doi.org/10.1109/focs.2017.36openalex-snapshot
A Dichotomy for Regular Expression Membership Testing
inferredcites →https://doi.org/10.1109/sffcs.1999.814642openalex-snapshot
Efficient testing of large graphs
inferredcites →https://doi.org/10.1109/tit.1978.1055927openalex-snapshot
Hiding information and signatures in trapdoor knapsacks
inferredcites →https://doi.org/10.1109/tit.1984.1056964openalex-snapshot
A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem
inferredcites →https://doi.org/10.1137/1.9781611973075.72openalex-snapshot
An Improved Construction of Progression-Free Sets
inferredcites →https://doi.org/10.1137/1.9781611973082.61openalex-snapshot
Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal
inferredcites →https://doi.org/10.1137/1.9781611973402.135openalex-snapshot
Finding orthogonal vectors in discrete structures
inferredcites →https://doi.org/10.1137/1.9781611974331.ch88openalex-snapshot
Subtree Isomorphism Revisited
inferredcites →https://doi.org/10.1137/1.9781611974782.141openalex-snapshot
Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications
inferredcites →https://doi.org/10.1137/1.9781611974782.68openalex-snapshot
A Faster Pseudopolynomial Time Algorithm for Subset Sum
inferredcites →https://doi.org/10.1137/1.9781611974782.69openalex-snapshot
A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
inferredcites →https://doi.org/10.1137/110853327openalex-snapshot
Pattern Matching under Polynomial Transformation
inferredcites →https://doi.org/10.1137/130910932openalex-snapshot
Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
inferredcites →https://doi.org/10.1137/140952636openalex-snapshot
Bounding the Running Time of Algorithms for Scheduling and Packing Problems
inferredcites →https://doi.org/10.1137/s0097539797315410openalex-snapshot
New Lower Bounds for Convex Hull Problems in Odd Dimensions
inferredcites →https://doi.org/10.1145/1066100.1066101openalex-snapshot
An improved exponential-time algorithm for k -SAT
inferredcites →https://doi.org/10.1145/1806689.1806725openalex-snapshot
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
inferredcites →https://doi.org/10.1145/1806689.1806735openalex-snapshot
Saving space by algebraization
inferredcites →https://doi.org/10.1145/1806689.1806772openalex-snapshot
Towards polynomial lower bounds for dynamic problems
inferredcites →https://doi.org/10.1145/210332.210337openalex-snapshot
Color-coding
inferredcites →https://doi.org/10.1145/2488608.2488669openalex-snapshot
Strong ETH holds for regular resolution
inferredcites →https://doi.org/10.1145/2488608.2488673openalex-snapshot
Fast approximation algorithms for the diameter and radius of sparse graphs
inferredcites →https://doi.org/10.1145/2746539.2746568openalex-snapshot
Clustered Integer 3SUM via Additive Combinatorics
inferredcites →https://doi.org/10.1145/2746539.2746594openalex-snapshot
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
inferredcites →https://doi.org/10.1145/2746539.2746612openalex-snapshot
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
inferredcites →https://doi.org/10.1145/2840728.2840746openalex-snapshot
Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
inferredcites →https://doi.org/10.1145/2897518.2897555openalex-snapshot
The 4/3 additive spanner exponent is tight
inferredcites →https://doi.org/10.1145/2925416openalex-snapshot
On Problems as Hard as CNF-SAT
inferredcites →https://doi.org/10.1145/3055399.3055466openalex-snapshot
Average-case fine-grained hardness
inferredcites →https://doi.org/10.1145/3055399.3055467openalex-snapshot
Faster space-efficient algorithms for subset sum and k-sum
inferredcites →https://doi.org/10.1145/321812.321823openalex-snapshot
Computing Partitions with Applications to the Knapsack Problem
inferredcites →https://doi.org/10.1145/800061.808737openalex-snapshot
Multi-party protocols
inferredcites →https://doi.org/10.1287/ijoc.15.1.42.15151openalex-snapshot
A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation
inferredcites →https://doi.org/10.1287/moor.17.1.36openalex-snapshot
Approximation Schemes for the Restricted Shortest Path Problem
inferredcites →https://doi.org/10.1287/opre.35.1.70openalex-snapshot
Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
inferredcites →https://doi.org/10.3233/faia336openalex-snapshot
Handbook of Satisfiability
inferredcites →https://doi.org/10.37236/546openalex-snapshot
Sets of Integers that do not Contain Long Arithmetic Progressions
inferredcites →https://doi.org/10.5555/2884435.2884524openalex-snapshot
Higher lower bounds from the 3SUM conjecture

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-1-4614-6624-6_86-1openalex-snapshot
Gomory Group Minimization Problem and Its Applications
inferred← citeshttps://doi.org/10.1007/s00236-023-00451-7openalex-snapshot
Approximating subset sum ratio via partition computations
inferred← citeshttps://doi.org/10.1007/s10107-026-02348-yopenalex-snapshot
An Improved Pseudopolynomial Time Algorithm for Subset Sum
inferred← citeshttps://doi.org/10.1007/s10618-023-00954-4openalex-snapshot
Column-coherent matrix decomposition
inferred← citeshttps://doi.org/10.1007/s10878-022-00928-0openalex-snapshot
Faster algorithms for k-subset sum and variations
inferred← citeshttps://doi.org/10.1016/j.cosrev.2026.100919openalex-snapshot
An invitation to “Fine-grained complexity of NP-complete problems”
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00138openalex-snapshot
Why we couldn’t prove SETH hardness of the Closest Vector Problem for even norms!
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00129openalex-snapshot
An Improved Pseudopolynomial Time Algorithm for Subset Sum
inferred← citeshttps://doi.org/10.1145/3577530.3577573openalex-snapshot
Early Work Maximization Problem on Two Machines Under a Grade of Service Provision
inferred← citeshttps://doi.org/10.1145/3618260.3649618openalex-snapshot
0-1 Knapsack in Nearly Quadratic Time
inferred← citeshttps://doi.org/10.1145/3618260.3649719openalex-snapshot
Knapsack with Small Items in Near-Quadratic Time
inferred← citeshttps://doi.org/10.1145/3618260.3649727openalex-snapshot
Approximating Partition in Near-Linear Time
inferred← citeshttps://doi.org/10.1145/3717823.3718284openalex-snapshot
Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
inferred← citeshttps://doi.org/10.1145/3798129.3800913openalex-snapshot
Tight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.