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

31–40 of 54 posts

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

#31

Post by pasquinelli »

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

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

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

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

#32

Post by thaumasiotes »

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…

Note that the solution dataflow objects to already operates in constant time on an average-case basis. There isn't room to make a complexity improvement.

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

#33

Post by antics »

dataflow wrote: post #30
antics wrote: post #13

Earlier quoted context omitted.

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 i…

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

In statistics, we generally separate asymptotic bounds—which usually make guarantees only asymptotically—from finite-decay bounds like Chernoff, which decay exponentially not only in the limit, but also at each particular finite n. The second is much rarer and much more powerful.

This is an important distinction here: we are not talking about an asymptotic limit of coin flips. Each and every round of coin flips reduces the probability of not having an answer exponentially.

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

Ok, no problem, it's up to you to decide if you want to use your own definition here.

But, FYI, in computability theory, it is definitely fair game and very common to "simulate" some computation with something that is either much more memory-intensive or compute-intensive, in either the deterministic or probabilistic case. For example, it's pretty common to add or remove memory and see whether the new "simulated" routine takes more or less compute power than the "standard" algorithm, and that is kind of what people are up to with the PSPACE stuff that is going on right now.

Using that lens—and this is entirely off the cuff, but in the 10 seconds of thinking, I believe probably mostly correct—this algorithm "simulates" a fair coin toss by using 1 extra bit of memory and O(p) compute, where p is the reciprocal of |0.5-|. You can choose p to be infinite but you can do that for a sorting algorithm too (and that is why both sorting and this algorithm have DoS implications). Is this the best we can do? Well, that's the problem we're studying with randomness exractors: given this imperfect source of randomness, can we extract perfect randomness out of it at all?

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

#34

Post by lovecg »

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…

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

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

#35

Post by zmgsabst »

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…

The difference is deterministic termination:

There is no N such that your algorithm is guaranteed to terminate before N flips — even for a single bit. The complexity class in the worst case (100% T) is infinite; it’s only the average cases that have something reasonable.

To borrow your phrasing:

If you only have a stochastic algorithm, I think you should have to say so.

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

#36

Post by dataflow »

antics wrote: post #33
dataflow wrote: post #30

Earlier quoted context omitted.

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 i…

> What do you mean by "exponentially, not asymptotically, but for finite n"? Exponential is by definition asymptotic and continues infinitely, no? In statistics, we generally separate asymptotic bounds—which usually make guarantees only asymptotically—from finite-decay bounds like Chernoff, which decay exponentially not only in the limit, but also at each particular finite n. The second is much rarer and much more po…

> In statistics, we generally separate asymptotic bounds—which usually make guarantees only asymptotically—from finite-decay bounds like Chernoff, which decay exponentially not only in the limit, but also at each particular finite n. The second is much rarer and much more powerful.

I don't know if you're using different terminology than I understand here, but I'm reading "exponential in the limit" to mean "eventually exponential", or in other words "there is some finite n_0 where for n > n_0 the decay becomes exponential"? In which case it basically means that the first n_0 tosses would have to be discarded? It's nice that that's not the case, I guess. Somehow I don't find myself blown away by this, but perhaps I'm misunderstanding what it means to be "exponential but only in the limit but not for finite n".

> in computability theory, it is definitely fair game and very common to "simulate" some computation with something that is either much more memory-intensive or compute-intensive, in either the deterministic or probabilistic case.

"Much" more is one thing, "arbitrarily more if you're unlucky" is another. I'm not an expert in computability theory by any means, but whenever I've heard of simulation in that context, it's been with a hard bound (whether constant, polynomial, or whatever). I've never heard it called simulation in a context where the simulator can take arbitrarily long to simulate step #2. Even if this is normal to those in the field, don't think the average person thinks of it this way -- I very much think most people would want their money back if they were sold a "simulator" that took arbitrarily long to get to step #2.

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

#37

Post by antics »

dataflow wrote: post #36
antics wrote: post #33

Earlier quoted context omitted.

> What do you mean by "exponentially, not asymptotically, but for finite n"? Exponential is by definition asymptotic and continues infinitely, no? In statistics, we generally separate asymptotic bounds—which usually make guarantees only asymptotically—from finite-decay bounds like Chernoff, which decay exponentially not only in the limit, but also at each particular finite n. The second is much rarer and much more po…

> In statistics, we generally separate asymptotic bounds—which usually make guarantees only asymptotically—from finite-decay bounds like Chernoff, which decay exponentially not only in the limit, but also at each particular finite n. The second is much rarer and much more powerful. I don't know if you're using different terminology than I understand here, but I'm reading "exponential in the limit" to mean "eventually…

What is our goal here? I'm willing to continue this discussion but after answering these questions and seeing your responses elsewhere it does not seem like your understanding is improving (e.g., still misunderstanding that the algorithm does not take "arbitrary" time), so I'm not sure you're getting the value here... If you want to continue maybe we should try you asking specific questions instead.

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

#38

Post by geysersam »

zmgsabst wrote: post #35
antics wrote: post #13

Earlier quoted context omitted.

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…

The difference is deterministic termination: There is no N such that your algorithm is guaranteed to terminate before N flips — even for a single bit. The complexity class in the worst case (100% T) is infinite; it’s only the average cases that have something reasonable. To borrow your phrasing: If you only have a stochastic algorithm, I think you should have to say so.

You can relax the constraints to bound the cost.

If I asked a someone gambling, does it matter if this coin is biased 0.0001%, they will probably say no. And just like that, the algorithm is now guaranteed to terminate.

It's a bit unfair to talk about the case (100% T) because in that case you don't have a source of randomness anymore, we've dropped the assumption that you have a source of randomness, and as expected you can't make one from nothing.

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

#39

Post by antics »

zmgsabst wrote: post #35
antics wrote: post #13

Earlier quoted context omitted.

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…

The difference is deterministic termination: There is no N such that your algorithm is guaranteed to terminate before N flips — even for a single bit. The complexity class in the worst case (100% T) is infinite; it’s only the average cases that have something reasonable. To borrow your phrasing: If you only have a stochastic algorithm, I think you should have to say so.

Kind of, kind of not. I think it's fair to argue a lot of theory people would argue that it is effectively guaranteed to terminate, for any reasonable definition of "guaranteed."

As I mention elsewhere, for a coin where P(H)=0.75, with 600 flips, the probability of not having received an answer is less than 1 divided by the number of atoms in the universe. While this is not 0, neither is the probability of the atoms of the coin lining up just right that it falls through the table, producing neither H or T. Theoretically and practically we do generally consider these kinds of things immaterial to the problem at hand, perhaps papering over them with terms-of-art like "with high/extremely high/arbitrarily high/ probability". They all mean roughly the same thing: this algorithm is "essentially guaranteed" to terminate after n flips.

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

#40

Post by Dylan16807 »

zmgsabst wrote: post #35
antics wrote: post #13

Earlier quoted context omitted.

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…

The difference is deterministic termination: There is no N such that your algorithm is guaranteed to terminate before N flips — even for a single bit. The complexity class in the worst case (100% T) is infinite; it’s only the average cases that have something reasonable. To borrow your phrasing: If you only have a stochastic algorithm, I think you should have to say so.

> the worst case (100% T)

You're no longer randomly flipping a coin to get heads or tails at that point. There's a good argument that this is not within the original scenario.

Post reply on HN