2 citations · 4 across the 7 of their papers we have counts for
4 papers · 1 filter
Near-Optimal Quantum Algorithms for String Problems
Shyan Akmal, Ce Jin
We study quantum algorithms for several fundamental string problems, including Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. Th…
MAJORITY-3SAT (and Related Problems) in Polynomial Time
Shyan Akmal, Ryan Williams
Majority-SAT is the problem of determining whether an input -variable formula in conjunctive normal form (CNF) has at least satisfying assignments. Majority-SAT and re…
Faster Algorithms for Bounded Tree Edit Distance
Shyan Akmal, Ce Jin
Tree edit distance is a well-studied measure of dissimilarity between rooted trees with node labels. It can be computed in time [Demaine, Mozes, Rossman, and Weimann, ICAL…
Improved Approximation for Longest Common Subsequence over Small Alphabets
Shyan Akmal, Virginia Vassilevska Williams
This paper investigates the approximability of the Longest Common Subsequence (LCS) problem. The fastest algorithm for solving the LCS problem exactly runs in essentially quadratic…