On the public citation graph
On Problems as Hard as CNF-SAT
0 signed · 102 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.
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.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1006/jcss.2001.1774openalex-snapshot
Which Problems Have Strongly Exponential Complexity?
inferredcites →https://doi.org/10.1007/3-540-08353-7_135openalex-snapshot
Graph-theoretic arguments in low-level complexity
inferredcites →https://doi.org/10.1007/978-3-540-30559-0_21openalex-snapshot
Exact (Exponential) Algorithms for the Dominating Set Problem
inferredcites →https://doi.org/10.1007/978-3-540-79723-4_18openalex-snapshot
The Time Complexity of Constraint Satisfaction
inferredcites →https://doi.org/10.1007/978-3-642-02927-1_59openalex-snapshot
Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
inferredcites →https://doi.org/10.1007/978-3-642-04128-0_50openalex-snapshot
Inclusion/Exclusion Meets Measure and Conquer
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-17493-3_20openalex-snapshot
Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting
inferredcites →https://doi.org/10.1007/978-3-642-31594-7_65openalex-snapshot
On the Limits of Sparsification
inferredcites →https://doi.org/10.1007/s00453-013-9759-2openalex-snapshot
Inclusion/Exclusion Meets Measure and Conquer
inferredcites →https://doi.org/10.1016/0196-6774(86)90032-5openalex-snapshot
Algorithms for maximum independent sets
inferredcites →https://doi.org/10.1016/j.ic.2005.05.001openalex-snapshot
Tight lower bounds for certain parameterized NP-hard problems
inferredcites →https://doi.org/10.1016/j.jalgor.2004.04.012openalex-snapshot
An algorithm for the satisfiability problem of formulas in conjunctive normal form
inferredcites →https://doi.org/10.1109/ccc.2003.1214416openalex-snapshot
The complexity of unique k-SAT: an isolation lemma for k-CNFs
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/ccc.2011.36openalex-snapshot
Non-uniform ACC Circuit Lower Bounds
inferredcites →https://doi.org/10.1109/focs.2007.26openalex-snapshot
On the Optimality of Planar and Geometric Approximation Schemes
inferredcites →https://doi.org/10.1109/focs.2007.50openalex-snapshot
Space-Efficient Identity Based EncryptionWithout Pairings
inferredcites →https://doi.org/10.1109/focs.2011.23openalex-snapshot
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
inferredcites →https://doi.org/10.1137/0110015openalex-snapshot
A Dynamic Programming Approach to Sequencing Problems
inferredcites →https://doi.org/10.1137/070683933openalex-snapshot
Set Partitioning via Inclusion-Exclusion
inferredcites →https://doi.org/10.1137/1.9781611973082.60openalex-snapshot
Slightly Superexponential Parameterized Problems
inferredcites →https://doi.org/10.1145/1250790.1250801openalex-snapshot
Fourier meets möbius: fast subset convolution
inferredcites →https://doi.org/10.1145/1552285.1552286openalex-snapshot
A measure & conquer approach for the analysis of exact algorithms
inferredcites →https://doi.org/10.1145/2635812openalex-snapshot
Exponential Time Complexity of the Permanent and the Tutte Polynomial
inferredcites →https://doi.org/10.1145/321105.321111openalex-snapshot
Dynamic Programming Treatment of the Travelling Salesman Problem
inferredcites →https://doi.org/10.1561/0400000033openalex-snapshot
On the Power of Small-Depth Computation
inferredcites →https://doi.org/10.1561/9781601983015openalex-snapshot
On the Power of Small-Depth Computation
inferredcites →https://doi.org/10.4230/lipics.fsttcs.2009.2326openalex-snapshot
A Fine-grained Analysis of a Simple Independent Set Algorithm
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/net.21825openalex-snapshot
Algorithms for node‐weighted Steiner tree and maximum‐weight connected subgraph
inferred← citeshttps://doi.org/10.1007/978-1-4471-5559-1_29openalex-snapshot
The M-Hierarchy, and XP-Optimality
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_519openalex-snapshot
Exact Algorithms and Strong Exponential Time Hypothesis
inferred← citeshttps://doi.org/10.1007/978-3-319-03898-8_18openalex-snapshot
A Completeness Theory for Polynomial (Turing) Kernelization
inferred← citeshttps://doi.org/10.1007/978-3-319-09284-3_7openalex-snapshot
Conditional Lower Bounds for Failed Literals and Related Techniques
inferred← citeshttps://doi.org/10.1007/978-3-319-12691-3_48openalex-snapshot
Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications
inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_519-1openalex-snapshot
Exact Algorithms and Strong Exponential Time Hypothesis
inferred← citeshttps://doi.org/10.1007/978-3-642-29344-3_17openalex-snapshot
Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2 n
inferred← citeshttps://doi.org/10.1007/978-3-642-31155-0_9openalex-snapshot
Deterministic Parameterized Connected Vertex Cover
inferred← citeshttps://doi.org/10.1007/978-3-642-33293-7_3openalex-snapshot
Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n
inferred← citeshttps://doi.org/10.1007/978-3-642-38233-8_10openalex-snapshot
Exponential Complexity of Satisfiability Testing for Linear-Size Boolean Formulas
inferred← citeshttps://doi.org/10.1007/978-3-642-39206-1_31openalex-snapshot
Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree
inferred← citeshttps://doi.org/10.1007/978-3-642-40313-2_72openalex-snapshot
Parameterized Algorithms for Module Motif
inferred← citeshttps://doi.org/10.1007/978-3-662-43948-7_4openalex-snapshot
Consequences of Faster Alignment of Sequences
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_19openalex-snapshot
The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems
inferred← citeshttps://doi.org/10.1007/978-3-662-48054-0_49openalex-snapshot
Maximum Minimal Vertex Cover Parameterized by Vertex Cover
inferred← citeshttps://doi.org/10.1007/978-3-662-48350-3_63openalex-snapshot
On the Equivalence among Problems of Bounded Width
inferred← citeshttps://doi.org/10.1007/978-3-662-49529-2_23openalex-snapshot
Faster Algorithms to Enumerate Hypergraph Transversals
inferred← citeshttps://doi.org/10.1007/s00224-014-9550-zopenalex-snapshot
Hardness of Approximation for Knapsack Problems
inferred← citeshttps://doi.org/10.1007/s00453-013-9759-2openalex-snapshot
Inclusion/Exclusion Meets Measure and Conquer
inferred← citeshttps://doi.org/10.1007/s00453-013-9796-xopenalex-snapshot
Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n
inferred← citeshttps://doi.org/10.1007/s00453-014-9910-8openalex-snapshot
A Completeness Theory for Polynomial (Turing) Kernelization
inferred← citeshttps://doi.org/10.1007/s00453-015-9981-1openalex-snapshot
Constrained Multilinear Detection and Generalized Graph Motifs
inferred← citeshttps://doi.org/10.1007/s10107-022-01783-xopenalex-snapshot
On the optimality of pseudo-polynomial algorithms for integer programming
inferred← citeshttps://doi.org/10.1016/j.dam.2016.11.016openalex-snapshot
The Graph Motif problem parameterized by the structure of the input graph
inferred← citeshttps://doi.org/10.1016/j.ic.2016.08.005openalex-snapshot
Parameterized algorithms for the Module Motif problem
inferred← citeshttps://doi.org/10.1016/j.ipl.2014.05.001openalex-snapshot
Faster deterministic Feedback Vertex Set
inferred← citeshttps://doi.org/10.1016/j.ipl.2015.11.008openalex-snapshot
Tight lower bounds for the Workflow Satisfiability Problem based on the Strong Exponential Time Hypothesis
inferred← citeshttps://doi.org/10.1016/j.ipl.2020.105980openalex-snapshot
On the complexity of detecting hazards
inferred← citeshttps://doi.org/10.1016/j.jcss.2016.01.001openalex-snapshot
Separating OR, SUM, and XOR circuits
inferred← citeshttps://doi.org/10.1016/j.jcss.2016.07.008openalex-snapshot
Strong partial clones and the time complexity of SAT problems
inferred← citeshttps://doi.org/10.1016/j.jda.2013.06.011openalex-snapshot
Exponential approximation schemata for some network design problems
inferred← citeshttps://doi.org/10.1016/j.tcs.2012.10.035openalex-snapshot
On exact algorithms for the permutation CSP
inferred← citeshttps://doi.org/10.1016/j.tcs.2015.03.021openalex-snapshot
On the hardness of labeled correlation clustering problem: A parameterized complexity view
inferred← citeshttps://doi.org/10.1016/j.tcs.2015.08.029openalex-snapshot
Parameterized and subexponential-time complexity of satisfiability problems and applications
inferred← citeshttps://doi.org/10.1016/j.tcs.2016.03.017openalex-snapshot
On finding rainbow and colorful paths
inferred← citeshttps://doi.org/10.1109/focs.2013.47openalex-snapshot
Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses
inferred← citeshttps://doi.org/10.1109/focs.2013.83openalex-snapshot
The Parity of Directed Hamiltonian Cycles
inferred← citeshttps://doi.org/10.1109/focs.2014.37openalex-snapshot
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
inferred← citeshttps://doi.org/10.1109/focs.2014.76openalex-snapshot
Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails
inferred← citeshttps://doi.org/10.1109/focs.2017.11openalex-snapshot
On the Quantitative Hardness of CVP
inferred← citeshttps://doi.org/10.1109/tqe.2022.3151137openalex-snapshot
A Grover Search-Based Algorithm for the List Coloring Problem
inferred← citeshttps://doi.org/10.1137/1.9781611974331.ch28openalex-snapshot
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
inferred← citeshttps://doi.org/10.1137/1.9781611976465.102openalex-snapshot
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
inferred← citeshttps://doi.org/10.1137/130947076openalex-snapshot
Known Algorithms for Edge Clique Cover are Probably Optimal
inferred← citeshttps://doi.org/10.1145/2488608.2488646openalex-snapshot
Fast hamiltonicity checking via bases of perfect matchings
inferred← citeshttps://doi.org/10.1145/2488608.2488673openalex-snapshot
Fast approximation algorithms for the diameter and radius of sparse graphs
inferred← citeshttps://doi.org/10.1145/2603088.2603121openalex-snapshot
Faster decision of first-order graph properties
inferred← citeshttps://doi.org/10.1145/2914642.2914650openalex-snapshot
Resiliency Policies in Access Control Revisited
inferred← citeshttps://doi.org/10.1145/3293465openalex-snapshot
On Problems Equivalent to (min,+)-Convolution
inferred← citeshttps://doi.org/10.1145/3357713.3384308openalex-snapshot
Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum
inferred← citeshttps://doi.org/10.1145/3506707openalex-snapshot
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
inferred← citeshttps://doi.org/10.22028/d291-25417openalex-snapshot
Sampling from discrete distributions and computing Fréchet distances
inferred← citeshttps://doi.org/10.24963/ijcai.2022/247openalex-snapshot
Fine-grained Complexity of Partial Minimum Satisfiability
inferred← citeshttps://doi.org/10.4230/lipics.esa.2016.69openalex-snapshot
Finding Large Set Covers Faster via the Representation Method
inferred← citeshttps://doi.org/10.4230/lipics.esa.2019.73openalex-snapshot
Equal-Subset-Sum Faster Than the Meet-in-the-Middle
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2013.20openalex-snapshot
Probably Optimal Graph Motifs
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2013.353openalex-snapshot
Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
inferred← citeshttps://doi.org/10.46298/dmtcs.6824openalex-snapshot
New Algorithms for Mixed Dominating Set
inferred← citeshttps://doi.org/10.48550/arxiv.1207.3622openalex-snapshot
Approximating the diameter of a graph
inferred← citeshttps://doi.org/10.48550/arxiv.1301.7250openalex-snapshot
The Parity of Directed Hamiltonian Cycles
inferred← citeshttps://doi.org/10.48550/arxiv.1306.3566openalex-snapshot
Faster deterministic Feedback Vertex Set
inferred← citeshttps://doi.org/10.48550/arxiv.1308.3520openalex-snapshot
Fixed-Parameter and Approximation Algorithms: A New Look
inferred← citeshttps://doi.org/10.48550/arxiv.1402.0054openalex-snapshot
Popular conjectures imply strong lower bounds for dynamic problems
inferred← citeshttps://doi.org/10.48550/arxiv.2006.10592openalex-snapshot
On the complexity of detecting hazards
inferred← citeshttps://doi.org/10.5555/2884435.2884463openalex-snapshot
Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs
inferred← citeshttps://doi.org/10.9734/psij/2015/18414openalex-snapshot
The Computational Limit to Quantum Determinism and the Black Hole Information Loss Paradox
showing the first 69 of 70 · page through all 70
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.