Fine-Grained Complexity Theory (Tutorial)
From MaRDI portal
Publication:5090450
DOI10.4230/LIPIcs.STACS.2019.4OpenAlexW2928577142MaRDI QIDQ5090450
Publication date: 18 July 2022
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10243/pdf/LIPIcs-STACS-2019-4.pdf
Related Items (8)
Reconstructing Words from Right-Bounded-Block Words ⋮ Fine-Grained Complexity of Regular Path Queries ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ Unnamed Item ⋮ Sublinear-time reductions for big data computing ⋮ Sublinear-time reductions for big data computing ⋮ Reconstructing Words from Right-Bounded-Block Words ⋮ Fine-grained complexity theory: conditional lower bounds for computational geometry
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On a class of \(O(n^ 2)\) problems in computational geometry
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
- If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
- A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
- On Problems Equivalent to (min,+)-Convolution
- ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
- (Gap/S)ETH hardness of SVP
- Fine-grained complexity for sparse graphs
- More consequences of falsifying SETH and the orthogonal vectors conjecture
- Towards tight approximation bounds for graph diameter and eccentricities
- Fine-grained reductions from approximate counting to decision
- SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
- Faster all-pairs shortest paths via circuit complexity
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Parameterized Algorithms
- Programming Techniques: Regular expression search algorithm
- A Theorem on Boolean Matrices
- On the complexity of \(k\)-SAT
This page was built for publication: Fine-Grained Complexity Theory (Tutorial)
