2 citations · 4 across the 7 of their papers we have counts for
14 papers
Node-Weighted Triangles: Faster and Simpler
Shyan Akmal, Nick Fischer
Weighted variants of triangle detection are an important object of study because of their prominence in fine-grained complexity. We revisit the Node-Weighted Triangle problem, wher…
Graph Coloring Below Guarantees via Co-Triangle Packing
Shyan Akmal, Tomohiro Koana
In the -Coloring Problem, we are given a graph on nodes, and tasked with determining if its vertices can be properly colored using colors. In this paper we study b…
A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
Amir Abboud, Shyan Akmal, Nick Fischer
We present the first truly subcubic, combinatorial algorithm for detecting an induced -cycle in a graph. The running time is on -node graphs, thus separating th…
Faster Edge Coloring by Partition Sieving
Shyan Akmal, Tomohiro Koana
In the Edge Coloring problem, we are given an undirected graph with vertices and edges, and are tasked with finding the smallest positive integer so that the edges…
Detecting Disjoint Shortest Paths in Linear Time and More
Shyan Akmal, Virginia Vassilevska Williams, Nicole Wein
In the -Disjoint Shortest Paths (-DSP) problem, we are given a weighted graph on nodes and edges with specified source vertices , and target vert…
An Enumerative Perspective on Connectivity
Shyan Akmal
Connectivity (or equivalently, unweighted maximum flow) is an important measure in graph theory and combinatorial optimization. Given a graph with vertices and , the con…
Faster Detours in Undirected Graphs
Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams +1
The -Detour problem is a basic path-finding problem: given a graph on vertices, with specified nodes and , and a positive integer , the goal is to determine if…
An Efficient Algorithm for All-Pairs Bounded Edge Connectivity
Shyan Akmal, Ce Jin
Our work concerns algorithms for an unweighted variant of Maximum Flow. In the All-Pairs Connectivity (APC) problem, we are given a graph on vertices and edges, and are…
A Local-to-Global Theorem for Congested Shortest Paths
Shyan Akmal, Nicole Wein
Amiri and Wargalla (2020) proved the following local-to-global theorem in directed acyclic graphs (DAGs): if is a weighted DAG such that for each subset of 3 nodes there is…
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…
On a Convex Set with Nondifferentiable Metric Projection
Shyan S. Akmal, Nguyen Mau Nam, J. J. P. Veerman
A remarkable example of a nonempty closed convex set in the Euclidean plane for which the directional derivative of the metric projection mapping fails to exist was constructed by…