Fine-Grained Complexity Theory (Tutorial)
From MaRDI portal
Recommendations
- On some fine-grained questions in algorithms and complexity
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Fine-grained complexity theory: conditional lower bounds for computational geometry
- Towards hardness of approximation for polynomial time problems
- Algorithm analysis through proof complexity
Cites work
- (Gap/S)ETH hardness of SVP
- A near-linear pseudopolynomial time algorithm for subset sum
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A Theorem on Boolean Matrices
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Faster all-pairs shortest paths via circuit complexity
- Fine-grained complexity for sparse graphs
- Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
- Fine-grained reductions from approximate counting to decision
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- scientific article; zbMATH DE number 3126094 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 7204473 (Why is no real title available?)
- If the current clique algorithms are optimal, so is Valiant's parser
- Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
- Lower bounds based on the exponential time hypothesis
- Matching triangles and basing hardness on an extremely popular conjecture
- More consequences of falsifying SETH and the orthogonal vectors conjecture
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- On a class of \(O(n^ 2)\) problems in computational geometry
- On Problems Equivalent to (min,+)-Convolution
- On some fine-grained questions in algorithms and complexity
- On the complexity of k-SAT
- Parameterized algorithms
- Programming Techniques: Regular expression search algorithm
- SETH-based lower bounds for subset sum and bicriteria path
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- Towards tight approximation bounds for graph diameter and eccentricities
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
Cited in
(16)- Fine-grained complexity theory: conditional lower bounds for computational geometry
- Reconstructing words from right-bounded-block words
- Sublinear-time reductions for big data computing
- Sublinear-time reductions for big data computing
- Fine-Grained Complexity of Regular Path Queries
- Reconstructing Words from Right-Bounded-Block Words
- Subsequences in bounded ranges: matching and analysis problems
- Combinatorial algorithms for subsequence matching: a survey
- Near-linear time and fixed-parameter tractable algorithms for tensor decompositions
- Parameterized lower bounds for the weighted vertex cover problem in trees
- Conditional lower bounds for dynamic geometric measure problems
- Conditional lower bounds for dynamic geometric measure problems
- Unbalanced triangle detection and enumeration hardness for unions of conjunctive queries
- Fine-grained complexity of regular path queries
- Can you link up with treewidth?
- Can you link up with treewidth?
This page was built for publication: Fine-Grained Complexity Theory (Tutorial)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090450)
