Wei_Dai comments on Probability Space & Aumann Agreement - Less Wrong

34 Post author: Wei_Dai 10 December 2009 09:57PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (70)

You are viewing a single comment's thread. Show more comments above.

Comment author: Wei_Dai 11 December 2009 09:52:22PM *  5 points [-]

I haven't read the whole paper yet, but here's one quote from it (page 5):

The dependence, alas, is exponential in 1 / (δ^3 ε^6), so our simulation procedure is still not practical. However, we expect that both the procedure and its analysis can be considerably improved.

Scott is talking about the computational complexity of his agreement protocol here. Even if we can improve the complexity to something that is considered practical from a computer science perspective, that will still likely be impractical for human beings, most of whom can't even multiply 3 digit numbers in their heads.