Shyan Akmal

Shyan Akmal

Postdoctoral Researcher

INSAIT

Welcome!

I am a postdoctoral researcher in Theoretical Computer Science at INSAIT.

I am interested in fine-grained complexity and algorithm design, and especially enjoy thinking about problems concerning graph algorithms, string algorithms, and applications of algebraic methods in computer science.

Previously, I completed my PhD in Theoretical Computer Science at MIT, advised by both Virginia Vassilevska Williams and Ryan Williams.

Prior to that, I received a B.S. in Computer Science & Mathematics from 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

Detecting Disjoint Shortest Paths in Linear Time and More

with Virginia Vassilevska Williams and Nicole Wein

ICALP 2024

arXiv Conference Proceedings

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.

An Enumerative Perspective on Connectivity

SOSA 2024

arXiv Conference Proceedings

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

ESA 2023

arXiv Conference Proceedings

A Local-to-Global Theorem for Congested Shortest Paths

with Nicole Wein

ESA 2023

arXiv Conference Proceedings

An Efficient Algorithm for All-Pairs Bounded Edge Connectivity

with Ce Jin

ICALP 2023
Algorithmica 2024

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

ITCS 2022
Algorithmica 2023

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

with Ryan Williams

FOCS 2021

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 enjoyed 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

ICALP 2021

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

ICALP 2021

arXiv Conference Proceedings

Quantifying controllability in temporal networks with uncertainty

with Savana Ammons, Maggie Li, Michael Gao, Lindsay Popowski, and Jim Boerkoel

Artificial Intelligence 2020 (Volume 289)

Journal Publication

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

Optimization Letters 2015 (Volume 9)

arXiv Journal Publication

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.

Dissertation

Parameterized Relaxations for Circuits and Graphs

PhD Thesis DSpace