When someone absolutely demands a combinatorial construction for linear-sized cut sparsifiers
Greg Bodwin
@gbodwin.bsky.social
Associate professor at UMich. I do theoretical computer science and graph theory.
RIP Fermat you would have loved \usepackage[margin=0.5\textwidth]{geometry}
I poured my soul into building this course last fall: 📚 Graph Algorithms via Graph Decomposition 📚 Graph decomposition has been a powerful framework in graph algorithms for over 20 years, but the literature is scattered and technical. Thus, I tried to organize part of it into one coherent story.
I really like this paper, one of my favorites in recent memory. Quick explainer of what's going on:
arXiv cs.DS Data Structures and Algorithms@csds-bot.bsky.social · 4mo agoSanjeev Khanna, Christian Konrad, Aaron Putterman: Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier https://arxiv.org/abs/2603.24530 https://arxiv.org/pdf/2603.24530 https://arxiv.org/html/2603.24530
I am thinking of starting a cult that believes that fast max flow algorithms might someday be used to produce paperclips in a manner that will destroy humanity. It's unfair that the AI subfield has monopolized this.
Academia hack: when writing scathing rejections, also demand that the authors add citations to your enemies
Hadas Weiss@hadas.bsky.social · 6mo agowhen reviewer 2 wants you to cite 3 texts by the same scholar
Kevin Pratt, Yahel Uffenheimer, Omri Weinstein: (Approximate) Matrix Multiplication via Convolutions https://arxiv.org/abs/2510.22193 https://arxiv.org/pdf/2510.22193 https://arxiv.org/html/2510.22193
I always thought it seemed weird how fancy waiters in movies would be like "Excellent choice, sir" after someone orders off a fixed menu. Now ChatGPT does this, and I can confirm: it is indeed weird
Some UMich TCS lore: a (now-retired) professor once photoshopped these shocked Hilberts to express his surprise at increasingly complicated Hilbert's Hotel situations. They are now in use as all-purpose math reactions. Please enjoy
Some questions on spanners in my talk at the Simons Institute. Since the talk, progress has been made on a few questions, but most are open. minorfree.github.io/SpannerQues/
Some Questions on Spanners | Rambling on Graphs
minorfree.github.io
adding a "Do you like this personality 👍👎" box to my email signature
Thinking about how the security people give their results metal names like "spectre" and "meltdown" and design cool logos for them. We should give that treatment to our theorems
Incredibly well deserved!!
Clément Canonne@ccanonne.github.io · last yr.Huge congratulations to Tracy Kimbrel, who received the 2025 ACM SIGACT Service Award 🏆 for his time, dedication, and advocacy as Program Director for the Algorithmic Foundations (AF) program at the NSF! sigact.org/prizes/servi... #TCSSky
Hot CS take: Big-O notation should have been defined to hide constant factor changes in the input variable, not the output function value
Huge congratulations to my amazing student Yeyuan Chen (+co-author Zihan Zhang of OSU advised by Zeyu Guo) for being awarded the STOC 2025 Best Student Paper Award! Their monumental result proves that explicit Reed-Solomon codes can correct more errors than previously known: arxiv.org/abs/2408.15925
Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds
In this paper, we prove that explicit FRS codes and multiplicity codes achieve relaxed generalized Singleton bounds for list size $L\ge1.$ Specifically, we show the following: (1) FRS code of length $...
arxiv.org
I find that this works, mostly, but requires the right amount of skepticism. Too much leads me to the “dual” of “fully trustful” reading, bogged down in doubting every little piece of ink, and not seeing the shapes or overall picture.
Greg Bodwin@gbodwin.bsky.social · last yr.A proof is a logical argument written to convince a skeptical audience. A corollary is that the best way to read a proof is to roleplay as a skeptical audience.
frantically changing "graph theory" to "autonomous killer graph theory" in all my papers
Chris Paxton@cpaxton.bsky.social · last yr.Amazing
This is terrible news, and part of the ongoing assault on science in the U.S. by the new administration. To honor Tracy Kimbrel and his service to the NSF's AF division, here's a short thread about a beautiful algorithm of his, joint with Rakesh Sinha (www.sciencedirect.com/science/arti...). 1/
A probabilistic algorithm for verifying matrix products using O(n2) time and log2n + O(1) random bits
sciencedirect.com
𝖬𝖺𝗁𝖽𝗂 𝖢𝗁𝖾𝗋𝖺𝗀𝗁𝖼𝗁𝗂@mahdi.ch · last yr.This seems to also include Tracy Kimbrel who served as a program manager for essentially all theoretical computer science for about 15 years :( Totally outrageous.
A proof is a logical argument written to convince a skeptical audience. A corollary is that the best way to read a proof is to roleplay as a skeptical audience.
Guy who updates his beliefs towards frequentism after witnessing examples of it working
One of my favourite things anyone has ever said about art. You'll be missed, David. 🌹
With @adamsmith.xyz and @thejonullman.bsky.social, we have compiled a set of profiles of 29 people in the "foundations of responsible computing" community ("mathematical research in computation and society writ large") who are on the faculty job market. Link: drive.google.com/file/d/1Hyvg... 1/3
In Vietnam they call these "dragon powder." That is so much cooler than "fire extinguisher" what are we doing
