Pages that link to "Item:Q5361845"
From MaRDI portal
The following pages link to Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made (Q5361845):
Displaying 23 items.
- Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence? (Q1705641) (← links)
- Partially local multi-way alignments (Q1993381) (← links)
- Satisfiability algorithm for syntactic read-\(k\)-times branching programs (Q2032296) (← links)
- A \#SAT algorithm for small constant-depth circuits with PTF gates (Q2118395) (← links)
- Tight conditional lower bounds for longest common increasing subsequence (Q2272597) (← links)
- Incremental delay enumeration: space and time (Q2274091) (← links)
- Longest common subsequence in sublinear space (Q2656347) (← links)
- Faster All-Pairs Shortest Paths via Circuit Complexity (Q4554074) (← links)
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False) (Q4571928) (← links)
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture (Q4571929) (← links)
- (Q4638059) (← links)
- Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds (Q4993300) (← links)
- (Q5002674) (← links)
- (Q5002720) (← links)
- From Circuit Complexity to Faster All-Pairs Shortest Paths (Q5009891) (← links)
- On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection (Q5041250) (← links)
- (Q5090378) (← links)
- (Q5090396) (← links)
- Fine-Grained Complexity Theory (Tutorial) (Q5090450) (← links)
- (Q5111874) (← links)
- Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs (Q5136279) (← links)
- The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance (Q5874533) (← links)
- (Q6084394) (← links)
