Why I'm rereading an undergraduate thesis I started writing 18 years ago
In 2008 I picked a thesis on derandomizing algorithms without knowing what it was. I reread it 18 years later: the mistakes, the context, and why these ideas underpin today's tech.
In 2008 I was a Computer Science student at UFPR and had to pick a topic for my undergraduate thesis. Back then it was pretty common for students to choose an advisor and for the advisor to more or less nudge you toward a topic in their field. Mine worked in theory of computation and suggested something called “derandomization of BPP algorithms.” I had no idea what that was, but I thought the name sounded nice and said yes with the confidence of someone who doesn’t grasp the size of the problem he’s just signed up for.
I ended up spending two years on it. Well, officially four semesters, but I failed two of them for not turning the work in on time, so let’s say two years of actual work spread across four semesters of existence. I wrote 42 pages. I defended it in December 2010, passed with a good grade (after two years thinking about the subject, something had to come out right), put the diploma on the shelf at my mom’s house, went off to work as a dev, and basically never looked at the thing again. It sat on an old university server, zipped, waiting for no one.
Last week I decided to reread it. The original thesis is online (in Portuguese), if you want to follow along.
What I found
I found out the thesis has mistakes. Some silly ones (the definition of a class written literally backwards, a swapped quantifier in a critical definition, the letter p equal to zero when it should be 1/2). Some conceptual. Some editorial decisions that aged badly. I found out that the central proof of the topic, the very reason the thesis exists, I marked with “this proof will be omitted” and moved on as if nothing had happened. At 27, with the deadline (once again) knocking at the door and sleeping 4 hours a night, I chose editorial cowardice. Today I’d call it a strategic scoping decision. Same thing in a nicer coat.
I also found out the thesis quotes the Bible in the introduction. Twice. Matthew and Luke. I’m not going to defend that. It was 2008, I was 24, I went to a church whose ideas were questionable even by the Bible’s standards, and I thought it fit the topic. It fits about as well as a Friday 6 p.m. deploy right before happy hour, but I was convinced.
But I also found something else, which is the reason this series exists.
I found out that that kid who didn’t speak English, using 2008-vintage Google Translate (which produced sentences like “the random walk is a drunk man’s stroll down the street” in contexts where that was definitely not the intended meaning), sitting alone in a library with a copy of Motwani-Raghavan open that he pretended to read but was actually deciphering word by word with a dictionary next to him (no, he didn’t have a laptop or a smartphone), that kid managed to understand and translate into Portuguese a field that, to this day, has almost no introductory material in the language.
The thesis has holes. But it also has the stubbornness of having been attempted under fairly unfavorable circumstances. That counts for something, even if it’s just “congrats on the persistence, now go fix the mistakes.”
The context that changed
I wouldn’t pick the same path today that I picked in 2008. Today I’d have ChatGPT or Claude to help me decipher a dense Motwani-Raghavan paragraph in minutes instead of entire afternoons. I’d have forums where people who know the subject answer specific questions for free. I’d have decent translators. I’d have Stanford and MIT lectures on exactly this topic, subtitled, on YouTube. I’d have books published after 2008 that organize much better what back then only existed scattered across lecture notes in dense English.
That means today’s undergrad, if they wanted to, would write a much better thesis on the same topic. It also means something less obvious: over the last 18 years, a lot of people from my generation produced academic work in Portuguese on hard technical topics, with disproportionate effort, and that work was forgotten on university servers because there was no channel for it to reach anyone beyond the thesis committee.
I probably have dozens of peers from my generation who wrote well-crafted theses and dissertations on interesting topics, and the total lifetime audience for that work was three tired professors in a room with no air conditioning. That’s intellectual heritage that existed, was produced with sweat, and evaporated into silence.
What I want to do here
This series is born from two connected ideas.
The first is to go back to my own thesis, not to fix it (it would be too late, and nobody reads undergrad theses anyway, not even their own authors), but to pull out of it what’s worth telling people outside the field. The mathematical ideas in there are beautiful, they’re powerful, they underpin a good chunk of the technology we use every day, and almost nobody outside academia knows they exist. I have the somewhat accidental advantage of having studied this when I was young and working in industry today, so I can translate from one world to the other without major trauma.
The second is broader. It’s an attempt to build a bridge between advanced theory of computation and the everyday life of people who use technology without ever wondering how it works under the hood. Without being too formal (college already does that, and nobody can stand it) and without being too shallow (popular science sometimes slips into “wow, so cool” without actually telling you anything). Aiming for an honest middle ground: real math, told with history, with people, with concrete applications.
I’m going to make mistakes. I’ll write posts that are too long, or simplify things to the point where someone more rigorous turns up their nose in the comments, and if that’s you, go for it, I’ll learn along the way. It comes with the territory. Explaining theory to people outside the field is the craft of being approximately right, because being exactly right is the textbook’s job, and nobody reads a textbook for fun.
A personal bet
There’s one thing I’ve learned over these 22 years of a career in software, and it’ll show up a lot around here: the math that seems most useless while you’re studying it tends to be exactly the math that saves you years later.
In 2008, that thesis on derandomization looked like the most disconnected-from-the-real-world thing I could possibly imagine. For all practical purposes, it was the intellectual equivalent of learning Latin: beautiful, rigorous, and, for me, completely useless. I was going to be a dev. I was going to work on Brazil’s electronic tax invoice systems, on CRUD screens, on clients calling about a production issue at 6 in the evening. What the hell was I going to do with “a pseudorandom generator indistinguishable from uniform in polynomial time”?
Well, guess what. Fifteen years after the defense, working with generative AI, recommendation systems, cryptography, distributed infrastructure, I found out that half of what passes for magic in the industry is a direct grandchild of those ideas. The kid thought he was studying something obscure. Without knowing it, he was studying the very everyday life he’d be living two decades later. If I could go back in time and warn him, he probably wouldn’t believe me and would stay focused on the dessert at the university cafeteria.
The lesson is kind of annoying to accept when you’re in the middle of college hating Linear Algebra: there’s no such thing as useless math. There’s math whose usefulness just hasn’t shown up yet.
The plan
There will be 3 posts on specific ideas.
The first is about a Russian-Latvian algorithm from 1977 that’s used today to check whether your R$ 15,000 GPU is computing GTA 5 frames correctly, or whether it quietly lost its mind halfway through the calculation.
The second is about why ChatGPT’s “creativity” is, technically, a very well-rehearsed mathematical performance, and why that’s not bad, just interesting.
The third is about how Google figured out which pages on the internet were important without reading any of them, using an imaginary, eternally bored web surfer.
They all have something in common: they’re ideas that were in my thesis back in 2008, when I thought they’d never be good for anything beyond getting me past the committee so I could sleep more than four hours a night.
Turns out they’re good for a little more than that. I’ll try to tell it properly this time.
Whether you’re a dev, an engineer, a student, just curious, or landed here by accident, make yourself at home. Comment, disagree, correct me, suggest topics. The format will adjust as we go.