No article text was recorded for this version.
conjecture-dependent hardness
Version 2 of 2328 papers364 conceptsfrozen 2026-10-04
Papers in this version
- Blog: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)
- Blog: On Complexity of 1-Center in Various Metrics
- Blog: Hardness of Approximation for Euclidean k-Median
- Blog: Near-Optimal UGC-hardness of Approximating Max k-CSP_R
- Blog: Linear FPT reductions and computational lower bounds
- Blog: PosSLP and Sum of Squares
- Blog: Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
- Blog: On Problems Equivalent to (min, +)-Convolution
- Blog: Lower Bounds for Multiplication via Network Coding
- Blog: New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
- Blog: On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
- Blog: Towards a Characterization of Approximation Resistance for Symmetric CSPs
- Blog: Majority Is Asymptotically the Most Stable Resilient Function
- Blog: Near-linear time subhypergraph counting in bounded degeneracy hypergraphs
- Blog: Conditional Hardness for Approximate Coloring
- Blog: Approximate Hypergraph Coloring under Low-discrepancy and Related Promises
- Blog: On the Subexponential Time Complexity of CSP
- Blog: Approximation Resistant Predicates From Pairwise Independence
- Blog: Simple Proof of Hardness of Feedback Vertex Set
- Blog: Lower Bounds for External Memory Integer Sorting via Network Coding
- Blog: On the Subexponential Time Complexity of CSP
- Blog: 2log1-έn Hardness for Closest Vector Problem with Preprocessing
- Blog: Inapproximability of Treewidth and Related Problems
- Blog: Agnostic Learning of Monomials by Halfspaces is Hard
- Blog: The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern.
- Blog: On Unique Games with Negative Weights
- Blog: Analysis of Boolean Functions
- Blog: The Complexity of Approximating Vertex Expansion
- Blog: Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment
- Blog: Conditionally Optimal Algorithms for Generalized Büchi Games
- Blog: Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six
- Blog: Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
- Blog: The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
- Blog: Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
- Blog: Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms
- Blog: Algorithms in 3-manifold theory
- Blog: Computational Complexity of Covering Disconnected Multigraphs
- Blog: A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems
- Blog: LP and SDP inapproximability of combinatorial problems
- Blog: The double exponential runtime is tight for 2-stage stochastic ILPs
- Blog: On the hardness of learning sparse parities
- Blog: A Characterization of Approximability for Biased CSPs
- Blog: Unique Games on the Hypercube
- Blog: A Fast Minimum Degree Algorithm and Matching Lower Bound
- Blog: Robust Approximation of Temporal CSP
- Blog: Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering
- Blog: On the robust hardness of Gröbner basis computation
- Blog: Tight Lower Bounds for Block-Structured Integer Programs
- Blog: When is the evaluation of conjunctive queries tractable?
- Blog: Strengthened Hardness for Approximating Minimum Unique Game and Small Set Expansion.
- Blog: Towards Tight Lower Bounds for Scheduling Problems
- Blog: On the Fine-Grained Hardness of Inverting Generative Models
- Blog: Hardness of Bichromatic Closest Pair with Jaccard Similarity
- Blog: Phylogenetic CSPs are Approximation Resistant
- Blog: Automates à contraintes semilinéaires = Automata with a semilinear constraint
- Blog: Inapproximability of Treewidth and Related Problems (Extended Abstract)
- Blog: Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant
- Blog: Fully-Dynamic Coresets
- Blog: Hardness of Approximate Nearest Neighbor Search under L-infinity
- Blog: Generalization of semi-regular sequences: Maximal Gröbner basis degree, variants of genericness, and related conjectures
Showing 60 of 328 papers.
History & citation
Current · Permanent link
- Noise Stability of Low Influence Boolean Functions merged into this direction (57% overlap)
- reliance on unproven conjectures split from this direction (54% overlap)
- MSO1 model-checking intractability split from this direction (60% overlap)
Cite this direction
Latest version (a living page):
@misc{lacuna_conjecture_dependent_hardness_d8fd7bf3,
title = {conjecture-dependent hardness},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/conjecture-dependent-hardness/rdr_d8fd7bf33b414d7e8bbba957e56fb5a7},
note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}This exact version (version 2, frozen text):
@misc{lacuna_conjecture_dependent_hardness_d8fd7bf3_v2,
title = {conjecture-dependent hardness},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/conjecture-dependent-hardness/rdr_d8fd7bf33b414d7e8bbba957e56fb5a7/v/2},
note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}