Shyan Akmal

Shyan Akmal

Computer Science PhD Student

Massachusetts Institute of Technology

Welcome!

I am a fourth-year PhD candidate studying Theoretical Computer Science at MIT, grateful to be advised by both Virginia Vassilevska Williams and Ryan Williams.

I am broadly 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 received a B.S. in Computer Science & Mathematics from Harvey Mudd College, where I was fortunate to have several excellent mentors. In particular, I am indebted to Mohamed Omar for helping foster my interest in combinatorics, Jim Boerkoel for showing me how fascinating computer science research could be, and Ran Libeskind-Hadas for sparking my interest in complexity theory.

You can contact me using the email listed here .

Publications

Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity

with Ce Jin, Lijie Chen, Malvika Raj, and Ryan Williams

ITCS 2022

ECCC Conference Proceedings

Near-Optimal Quantum Algorithms for String Problems

with Ce Jin

SODA 2022 & QIP 2022

arXiv Conference Proceedings

with Ryan Williams

FOCS 2021

arXiv Conference Extended Abstract A Twitter Thread Oxford-Warwick Presentation Slides LIS Natural Computation Presentation UWaterloo Solvers, ML, Logic, & Complexity Presentation FOCS Video

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

Problem of the Fortnight

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. Every two weeks I will post a recreational (non-research) math problem which I encountered during this time (and particularly enjoyed) below.

 

Convergence Only on Primes

Does there exist an infinite sequence of complex numbers $a_1, a_2, \dots$ such that for any positive integer $p$, the sum

$$\sum_{n=1}^{\infty} a_n^p$$

converges if and only if $p$ is prime?

 

A new problem will be posted here on December 17th, 2022.

Previously posted problems can be found here.