Shyan Akmal
Postdoctoral Fellow
MPI
Welcome!
I am a postdoctoral fellow in Theoretical Computer Science at the Max Planck Institute for Informatics. My research is in algorithm design, and I especially enjoy thinking about problems concerning graph algorithms, string algorithms, fine-grained complexity, parameterized complexity, and applications of algebraic methods in computer science.
Previously, I was a posdoctoral researcher at INSAIT supervised by Bernhard Haeupler. Prior to that, I completed my PhD at MIT, advised by both Virginia Vassilevska Williams, and Ryan Williams, and my B.S. at Harvey Mudd College. I have been fortunate to have several excellent mentors and, in particular, am indebted to JJP Veerman, Mohamed Omar, Jim Boerkoel, and Ran Libeskind-Hadas for sparking my interest in research.
You can contact me using the email listed here .
Publications
A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
with Amir Abboud and Nick Fischer
Graph Coloring Below Guarantees via Co-Triangle Packing
with Tomohiro Koana
Faster Edge Coloring by Partition Sieving
with Tomohiro Koana
Detecting Disjoint Shortest Paths in Linear Time and More
with Virginia Vassilevska Williams and Nicole Wein
If you are interested in learning about the linear-time algorithms for $\textsf{2-Disjoint Shortest Paths}$ discussed in this work, you may find the exposition in chapters six and eight of my thesis easier to follow. If you like this paper, you may also enjoy reading this work by Keerti Choudhary, Amit Kumar, and Lakshay Saggi, which applies similar algebraic techniques to solve more general problems.
An Enumerative Perspective on Connectivity
SOSA 2024
TheoretiCS 2024 · Invited to Special Issue
arXiv Conference Proceedings Journal Publication
Instead of reading this paper, you may find the exposition in chapters six and seven of my thesis easier to follow.
Faster Detours in Undirected Graphs
with Virginia Vassilevska Williams, Ryan Williams, and Zixuan Xu
A Local-to-Global Theorem for Congested Shortest Paths
with Nicole Wein
An Efficient Algorithm for All-Pairs Bounded Edge Connectivity
with Ce Jin
arXiv Conference Proceedings Journal Publication
Instead of reading this paper, you may find the exposition in chapters six and seven of my thesis easier to follow.
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity
with Ce Jin, Lijie Chen, Malvika Raj, and Ryan Williams
ECCC Conference Proceedings Journal Publication
Near-Optimal Quantum Algorithms for String Problems
with Ce Jin
SODA 2022
QIP 2022
Algorithmica 2023
arXiv Conference Proceedings Journal Publication
MAJORITY-3SAT (and Related Problems) in Polynomial Time
with Ryan Williams
arXiv Conference Extended Abstract A Nitter Thread Oxford-Warwick Presentation Slides LIS Natural Computation Presentation UWaterloo Solvers, ML, Logic, & Complexity Presentation FOCS Video
Instead of reading this paper, you may find the exposition in Part I of my thesis easier to follow.
If you like this paper, you may also enjoy this beautiful sequel work by Till Tantau.
Improved Approximation for Longest Common Subsequence over Small Alphabets
with Virginia Vassilevska Williams
arXiv Conference Proceedings SM Thesis Version Presentation
The main open problem raised by this work was resolved in this paper by Xiaoyu He and Ray Li.
Faster Algorithms for Bounded Tree Edit Distance
with Ce Jin
If you like this work, you may also be interested in checking out this paper by Tomasz Kociumaka and Ali Shahali, which (among other results) simplifies the analysis of our algorithm and observes it applies to the weighted variant of tree edit distance as well.
Quantifying controllability in temporal networks with uncertainty
with Savana Ammons, Maggie Li, Michael Gao, Lindsay Popowski, and Jim Boerkoel
Quantifying Degrees of Controllability in Temporal Networks with Uncertainty
with Savana Ammons, Maggie Li, and Jim Boerkoel
ICAPS 2019 · Runner-Up for Best Student Paper
Conference Proceedings Presentation
On a Convex Set with Nondifferentiable Metric Projection
with Nguyen Mau Nam and J. J. P. Veerman
Recreational Math
During high school I participated in a few math contests, and in undergrad I wrote several problems for the Caltech Harvey Mudd Math Competition and USA Math Talent Search.
Some recreational (non-research) math problems which I particularly enjoyed from this time can be found here.