Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The new Gödel Prize winner tastes great and is less filling

blog.computationalcomplexity.org

Post reply on HN
Print view View original

21–30 of 54 posts

Re: The new Gödel Prize winner tastes great and is less filling

#21

Post by Terr_ »

pbhjpbhj wrote: post #15
antics wrote: post #3

If 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.

Speaking 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' t…

I 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.

Re: The new Gödel Prize winner tastes great and is less filling

#22

Post by antics »

dataflow wrote: post #12
QuesnayJr wrote: post #11

Earlier quoted context omitted.

I have the exact opposite reaction, that if someone told me the answer is "no" because it requires an unbounded number of coin flips that they were the ones trying to bullshit me. In antic's formulation, nothing is said about requiring a bounded number of flips.

"Simulate a truly random coin" implies it IMO. You're not simulating a truly random coin if you need unbounded time for a single flip. The truly random coin definitely doesn't need that. It just feels like a scam if someone sold me such a machine with that description - I'd want my money back. I don't expect everyone would feel the same, but I think a lot of people would.

I'm not sure we're on the same page about what this result practically means, so let me re-state it a few different ways, so that people can draw their own conclusions:

* The von Neumann approach will "appear to be O(1) (constant-time)" for any particular biased coin, but that constant might be big if the coin is very, VERY biased in one direction.

* How can this be true? Every flip reduces the probability you do not have an answer exponentially. The "concentration" around the mean is very sharp—e.g., at 275 coin tosses for P(H)=0.5 (the fair case), the probability of not having an answer is smaller than 1 divided by the number of atoms in the known universe. It is technically possible, but I think most people would say that it's "effectively constant time" in the sense that we'd expect the coin to phase-shift through the desk before flipping it 275 times in a row and not getting answer. So it takes 275 flips, it's "constant" time! Interpret it how you like though.

* As you make the coin more and more biased, that "horizon" increases linearly, in that 0.99^1,000 is approximately the same thing as 0.999^10,000. So, an order of magnitude increase in probability requires roughly an order of magnitude increase in the number of flips. This is why it's not useful for the adversarial case, and why adversarial extractors are held apart from normal extractors.

Whether this is a "give me my money back" type thing is for you to decide. I think for most people the claim that you can simulate a fair coin from a biased coin in, effectively, O(1), and that the constant increases in O(n) in the bias, is plainly incredible. :)

Re: The new Gödel Prize winner tastes great and is less filling

#23

Post by Dylan16807 »

dataflow wrote: post #20
thaumasiotes wrote: post #16

Earlier quoted context omitted.

You don't need unbounded time for a single flip, that's all in your imagination. The worst-case time is unbounded, but you can't achieve the worst case.

> You don't need unbounded time for a single flip, that's all in your imagination. The worst-case time is unbounded, but you can't achieve the worst case. There literally isn't a bound, it can be arbitrarily large. This isn't just in my head, it's a fact. If it's bounded in your mind then what is the bound?

It's not a fact of the real world, at least. "You can't achieve it" is true. A pretty small number of failures and you're looking at a trillion years to make it happen. And if you buffer some flips that number gets even smaller.

Re: The new Gödel Prize winner tastes great and is less filling

#24

Post by dooglius »

dataflow wrote: post #12
QuesnayJr wrote: post #11

Earlier quoted context omitted.

I have the exact opposite reaction, that if someone told me the answer is "no" because it requires an unbounded number of coin flips that they were the ones trying to bullshit me. In antic's formulation, nothing is said about requiring a bounded number of flips.

"Simulate a truly random coin" implies it IMO. You're not simulating a truly random coin if you need unbounded time for a single flip. The truly random coin definitely doesn't need that. It just feels like a scam if someone sold me such a machine with that description - I'd want my money back. I don't expect everyone would feel the same, but I think a lot of people would.

A real coin could repeatedly land on its side over and over indefinitely, every time you flipped it.

Re: The new Gödel Prize winner tastes great and is less filling

#25

Post by dataflow »

Dylan16807 wrote: post #23
dataflow wrote: post #20

Earlier quoted context omitted.

> You don't need unbounded time for a single flip, that's all in your imagination. The worst-case time is unbounded, but you can't achieve the worst case. There literally isn't a bound, it can be arbitrarily large. This isn't just in my head, it's a fact. If it's bounded in your mind then what is the bound?

It's not a fact of the real world, at least. "You can't achieve it" is true. A pretty small number of failures and you're looking at a trillion years to make it happen. And if you buffer some flips that number gets even smaller.

> A pretty small number of failures and you're looking at a trillion years to make it happen.

This depends on the bias of the original coin. P(H) can be arbitrarily large, making P(HH) the likeliest possibility even for a trillion years. "This wouldn't happen in the real world" would be a sorry excuse for the deliberate refusal to clearly state the problem assumptions upfront.

IMO, if you really want to pleasantly surprise people, you need to be forthcoming and honest with them at the beginning about all your assumptions. There's really no good excuse to obfuscate the question and then move the goalposts when they (very predictably) fall into your trap.

Re: The new Gödel Prize winner tastes great and is less filling

#27

Post by dwattttt »

dataflow wrote: post #9
antics wrote: post #8

Earlier quoted context omitted.

While 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.

Note 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),…

I don't think anyone would be surprised to hear that if a biased coin can only give one result, you can't extract randomness from it.

And if it can only give the second result one in a million times, you could be flipping millions.

Re: The new Gödel Prize winner tastes great and is less filling

#28

Post by Dylan16807 »

dataflow wrote: post #25
Dylan16807 wrote: post #23

Earlier quoted context omitted.

It's not a fact of the real world, at least. "You can't achieve it" is true. A pretty small number of failures and you're looking at a trillion years to make it happen. And if you buffer some flips that number gets even smaller.

> A pretty small number of failures and you're looking at a trillion years to make it happen. This depends on the bias of the original coin. P(H) can be arbitrarily large, making P(HH) the likeliest possibility even for a trillion years. "This wouldn't happen in the real world" would be a sorry excuse for the deliberate refusal to clearly state the problem assumptions upfront. IMO, if you really want to pleasantly su…

> This depends on the bias of the original coin. P(H) can be arbitrarily large

> There's really no good excuse to obfuscate the question and then move the goalposts when they (very predictably) fall into your trap.

Interesting. Because I see the guy pulling out the one-in-a-million coin and expecting it to run at a similar speed to be doing a gotcha on purpose, not falling into a trap and having the goalposts moved.

And I think "well if it's a million times less likely to give me a heads, then it takes a million times as many flips, but it's just as reliable" is an answer that preserves the impressiveness and the goalposts.

It's fast relative to the bias. Which seems like plenty to me when the original claim never even said it was fast.

(And if the coin never gives you a heads then I'd say it no longer qualifies as randomly flipping a coin.)

Re: The new Gödel Prize winner tastes great and is less filling

#29

Post by NooneAtAll3 »

I 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?

Re: The new Gödel Prize winner tastes great and is less filling

#30

Post by dataflow »

antics wrote: post #13
dataflow wrote: post #9

Earlier quoted context omitted.

Note 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),…

So, the problem in its original framing is: can we simulate a fair coin flip with an unfair coin? As stated, I do actually think the von Neumann response answer ("this is actually technically possible") is fair, in that if I wanted a solution in O(1), I think I should have to say so ahead of time. I suppose we'll have to disagree about whether this is incredible. The response shows that (1) this can be done at all, a…

What do you mean by "exponentially, not asymptotically, but for finite n"? Exponential is by definition asymptotic and continues infinitely, no?

And to be clear, I'm not disagreeing (or agreeing) with the result being inherently incredible. I'm just saying it's not an incredible example of simulating a fair coin, because it just... isn't doing that. As an analogy: communicating with the Voyager spacecraft might be incredible, but it's not an incredible example of infinitely fast communication... because it just isn't. Telling me to go ask a room full of people whether they find either of these incredible is missing the point.

Post reply on HN