The new Gödel Prize winner tastes great and is less filling
110 points by baruchel 3 weeks ago | 47 comments- NooneAtAll3 3 weeks agoI feel like this blogpost isn't filling either
What exactly was the awarded paper about? What does "extractor" and "resilient function" mean?
Why did the discussion shift towards Ramsey theory? Why waste half of the post arguing about something already discussed in linked previous blogposts?
- HPMOR 3 weeks agoWow, crazy randomly seeing my Algo prof at the top of HN winning this! Congrats Eshan!!
- bhasi 3 weeks agoEshan's Bachelor's thesis advisor from IIT Kanpur, Prof Manindra Agrawal, also won the Gödel prize in 2006. Wow.
- Horde 3 weeks agoThis just generally reminded me about STOC. Need to read the last few years of the proceedings. I totally forgot about it. I like that 2026 will be held in the US. Some very fun to read papers at STOC. Even if they seem narrowly technical.
- antics 3 weeks agoIf I give you a biased coin can you simulate a truly random coin flip with it? The answer turns out to be yes. Flip the biased coin twice: HT = heads, TH = tails, and HH/TT = flip twice again.
The general study of such things is called “randomness extractors”. The new Gödel prize goes to this paper which shows how to extract a nearly perfect random bit out of two sources with low min-entropy.
- falcor84 3 weeks agoYes, but - you need to replace "twice" there with "an unbounded number of times". If you apply this in an environment where the biased coin is coming from an external source, your system becomes susceptible to DoS attacks.
- antics 3 weeks agoWhile I obviously think randomness extractors over adversarial sources are very interesting, I think talking about them specifically in this example complicates the point I'm trying to make, which is that it's incredible it can be done at all.
- dataflow 3 weeks agoNote that adversarial is kind of a red herring, not sure why they mentioned that. The number of flips is unbounded regardless. Which is why it's not really incredible that it can be done: it can't, not as the problem was originally stated. What can be done is solving a different (but useful) problem than the one originally posed.
I realize this sounds like a minor detail to someone who finds this cool (and so do I), but I don't think it is. It's kind of frustrating to be told that your intuition is wrong by someone smarter than you, when your intuition is actually correct and the experts are moving the goalposts. IMO, it makes people lose respect for experts/authority.
- dataflow 3 weeks ago
- pasquinelli 3 weeks agoi read "flip twice" as recussion, so, given we're talking randomness, yes, that could go on forever. but i don't think you really need to replace "twice."
- antics 3 weeks ago
- pbhjpbhj 3 weeks agoSpeaking from complete ignorance, with apologies to those who that will annoy:
I'm sure it's possible to make a coin with what one might term "complex bias" where the bias extends over two events (thick gloop inside the coin, possibly heat activated or non-Newtonian).
This method sounds like the bias needs to be fixed ("simple bias" if you like)?
I guess that's just out of scope here.
Aside: There's a strong 'vibe' that HHHH HHHH with a single coin is somehow less random than HTHTHTHT HTHTHTHT with two coins when discarding HH and TT. I wonder what the origin of that feeling is - maybe just HT doesn't seem like it's a constant result simply due to nomenclature? If we call HT "type-A", then we just have HHHH HHHH vs. AAAA AAAA; and I _feel_ happier about the result!
- Terr_ 3 weeks agoI suspect this depends on where you drawn the upper bound, since a really really complex biased coin is one that spies on your thesis and data and is committed to making you suffer.
Descartes' evil demon, in numismatic form.
- lovecg 3 weeks agoCould the vibe be due to the fact that HHHH… seems like the coin could not just be biased - it could be completely broken and come up heads every time. There are two distinct possibilities here:
1) the coin is broken and is always H
2) the coin is random or possibly biased, and you got a string of H by chance
And observing the string of H… increases the probability of 1) in the Bayesian sense.
With the two coins you eliminate this possibility altogether - a broken coin can never produce HT or TH.
- Terr_ 3 weeks ago
- 3 weeks ago
- falcor84 3 weeks ago
- doctorpangloss 3 weeks agoIt’s tough. You take Math 55, you’re a smart kid, you learn all this math, and it opens up all these opportunities from VCs in the real world for you, so long as it has to do with payments.
- unkeen 3 weeks ago[flagged]