Mihai Pătrașcu Best Paper Award: Guest post from Seth Pettie
Scott’s foreword: Today I’m honored to turn over Shtetl-Optimized to a guest post from Michigan theoretical computer scientist Seth Pettie, who writes about a SOSA Best Paper Award newly renamed in honor of the late Mihai Pătrașcu. Mihai, who I knew from his student days, was a brash, larger-than-life figure in theoretical computer science, for a brief few years until brain cancer tragically claimed him at the age of 29. Mihai and I didn’t always agree—indeed, I don’t think he especially liked me, or this blog—but as I wrote when he passed, his death made any squabbles seem trivial in retrospect. He was a lion of data structures, and it’s altogether fitting that this award be named for him. –SA
Seth’s guest post:
The SIAM Symposium on Simplicity in Algorithms (SOSA) was created in 2018 and has been awarding a Best Paper Award since 2020. This year the Steering Committee renamed this award after Mihai Pătrașcu, an extraordinary researcher in theoretical computer science who passed away before his time, in 2012.
Mihai’s research career lasted just a short while, from 2004-2012, but in that span of time he had a huge influence on research in geometry, graph algorithms, data structures, and especially lower bounds. He revitalized the entire areas of cell-probe lower bounds and succinct data structures, and laid the foundation for fine-grained complexity with the first 3SUM-hardness proof for graph problems. He lodged the most successful attack to date on the notorious dynamic optimality conjecture, then recast it
as a pure geometry problem. If you are too young to have met Mihai personally, I encourage you to pick up one of his now-classic papers. They are a real joy to read—playful and full of love for theoretical computer science.
The premise of SOSA is that simplicity is extremely valuable, rare, and inexplicably undervalued. We wanted to create a venue where the chief metrics of success were simplicity and insight. It is fitting that the SOSA Best Paper Award be named after Mihai. He brought “fresh eyes” to every problem he worked on, and showed that the cure for our problems is usually one key insight (and of course some mathematical gymnastics).
Let me end by thanking the SOSA 2026 Program Committee, co-chaired by Sepehr Assadi and Eva Rotenberg, and congratulating the authors of the SOSA 2026 Mihai Pătrașcu Best Paper:
- A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
Ajaykrishnan E S, Robert Ganian, Daniel Lokshtanov, Vaishali Surianarayanan
This award will be given at the SODA/SOSA business meeting in Vancouver, Canada, on January 12, 2026.
Follow
Comment #1 December 2nd, 2025 at 4:22 am
So quasi-polynomial-time algorithms have not merely become accepted (or rather “expected”) as a realistic posibility for problems where no polynomial-time algorithms are known, but even establishing quasi-polynomial lower bounds no longer feels unrealistic. I am curious about [3, 10, 9]:
Hmm, 2014, 2015, and 2017, so this stuff is definitively no longer new. Reminds me of the quadratic lower bound for edit distance.
And I wonder whether the existence of a polynomial-time quantum algorithm for factoring might be a reason why “classic ways” to establish the non-existence of a polynomial-time algorithm fail for factoring. And whether something analogous to the quadratic lower bound for edit distance (or those quasi-polynomial lower bounds) could exist.
But somehow those questions that were so important to me around 2015 no longer seem to matter in times of Sam Altman, Vladimir Putin, and global hype bubbles.
Comment #2 December 2nd, 2025 at 11:23 am
Simplicity in math and sciences is wonderful but it is often is only “simple” after the fact. Someone first found it and showed it to others but before the fact iit was difficult to see. I again think of the boson sampling idea. Various parties spending time and effort to demonstrate quantum supremacy and with the right idea (boson sampling) it became relatively simple to demonstrate. Simplicity can be like a trap door, easy to verify but difficult to first see.
Comment #3 December 4th, 2025 at 6:24 am
I am just an engineer but was always amazed at how much math resulted from the four simple axioms of group theory but in awe of what resulted from the two simple axioms of special relativity and the two of general relativity. Complexity can find seed in such simplicity.
Comment #4 December 4th, 2025 at 4:51 pm
OhMyGoodness#3: Those aren’t quite the same kind of thing, though. The physics axioms depend on all sorts of pre-existing concepts (inertial frames, speed of light, gravity, mass, and energy) and don’t really make sense without a whole bundle of theory about what those concepts mean. Whereas for the group axioms it’s literally just “you have a two-input operator on a set that satisfies these four properties”.
Comment #5 December 6th, 2025 at 10:35 am
Dacyn #4
Yes I agree..but…abstract mathematical structures need only be internally consistent with no external constraints like predicting the apparent position of mercury, providing the reason why short lived particles traveling near the speed of light have apparent extended life, the nature of Sag A., etc. it is not possible to look at the simply stated premises of relativity and know what comes from them. Even Einstein didn’t believe some of the implications that were later proven to be actual.
I apologize if I insulted your abstract mathematical sensibilities by mentioning abstract mathematics and real world physics together as an analogy in a certain sense. 🙂
Comment #6 December 6th, 2025 at 5:50 pm
OhMyGoodness #5: No apology necessary, I just felt like making a clarification 🙂