scientific article; zbMATH DE number 7758340
From MaRDI portal
Publication:6084394
DOI10.4230/lipics.approx/random.2020.38arXiv2006.13449MaRDI QIDQ6084394
Diptarka Chakraborty, Amey Bhangale, Rajendra Kumar
Publication date: 31 October 2023
Full work available at URL: https://arxiv.org/abs/2006.13449
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Cites Work
- Unnamed Item
- Unnamed Item
- New tabulation and sparse dynamic programming based techniques for sequence similarity problems
- A faster algorithm computing string edit distances
- Optimization, approximation, and complexity classes
- Expected length of the longest common subsequence for large alphabets
- Detecting high log-densities
- Graph expansion and the unique games conjecture
- Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths
- The Complexity of Some Problems on Subsequences and Supersequences
- A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
- Algorithms on Strings, Trees and Sequences
- The String-to-String Correction Problem
- ETH Hardness for Densest-k-Subgraph with Perfect Completeness
- On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
- Reducing approximate Longest Common Subsequence to approximate Edit Distance
- Synchronization strings: explicit constructions, local decoding, and applications
- Approximating LCS in Linear Time: Beating the √n Barrier
- Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- The dense \(k\)-subgraph problem
- On the complexity of \(k\)-SAT
