Shyan Akmal
Computer Science PhD Student
Massachusetts Institute of Technology
Welcome!
I am a third-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
Near-Optimal Quantum Algorithms for String Problems
with Ce Jin
MAJORITY-3SAT (and Related Problems) in Polynomial Time
with Ryan Williams
arXiv Conference Extended Abstract A Twitter Thread Oxford-Warwick Presentation Slides LIS Natural Computation Presentation UWaterloo Solvers, ML, Logic, & Complexity Presentation FOCS Video
Improved Approximation for Longest Common Subsequence over Small Alphabets
with Virginia Vassilevska Williams
arXiv Conference Proceedings SM Thesis Version Presentation
Faster Algorithms for Bounded Tree Edit Distance
with Ce Jin
Quantifying controllability in temporal networks with uncertainty
with Savana Ammons, Maggie Li, Michael Gao, Lindsay Popowski, and Jim Boerkoel
Artificial Intelligence 2020 (Volume 289)
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
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.
Regular Polygons Made Out Of Regular Polygons
Let $P$ be a regular polygon (i.e. an equiangular, equilateral polygon with at least three vertices). The vertices of $P$ are partitioned into a collection $\mathcal{C}$ of at least two sets $S$, with the property that the vertices in any such set $S$ can be connected to form a regular polygon. Prove that either $\mathcal{C}$ has only one set, or there exist two distinct sets in $\mathcal{C}$ of the same size.
In other words, prove that if a regular polygon can be decomposed into multiple smaller regular polygons, than at least two of the smaller regular polygons must have the same number of vertices.
A new problem will be posted here on July 8th, 2022.
Previously posted problems can be found here.