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

11–20 of 54 posts

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

#11

Post by QuesnayJr »

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

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

#12

Post by dataflow »

QuesnayJr wrote: post #11
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),…

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.

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

#13

Post by antics »

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

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, and (2) that the answer is exponentially likely as time goes on, not asymptotically, but for finite n. Incredible! You don't see finite-decay bounds very often! If you don't think that's incredible I invite you to ask a room full of people, even with the qualifications you deem appropriate, e.g., "solution does not need to be constant-time", or whatever.

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

#15

Post by pbhjpbhj »

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' 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!

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

#16

Post by thaumasiotes »

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.

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.

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

#17

Post by falcor84 »

thaumasiotes wrote: post #16
dataflow wrote: post #12

Earlier quoted context omitted.

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

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.

It's very easy to achieve if someone hands you a "coin" that is made such that it never lands on tails.

Sorry for still being in the adversarial mindset, but this means that you essentially have to hardcode a maximum number of same-side flips after which you stop trusting the coin.

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

#19

Post by Dylan16807 »

falcor84 wrote: post #17
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.

It's very easy to achieve if someone hands you a "coin" that is made such that it never lands on tails. Sorry for still being in the adversarial mindset, but this means that you essentially have to hardcode a maximum number of same-side flips after which you stop trusting the coin.

That's not a situation of "can't be done", that's just a consequence of casually describing the problem instead of exhaustively specifying it.

Yes the bias has to be finite / the entropy can't be zero, and the slowdown is related to how big the bias is / how low the entropy is.

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

#20

Post by dataflow »

thaumasiotes wrote: post #16
dataflow wrote: post #12

Earlier quoted context omitted.

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

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?

Post reply on HN