tag:blogger.com,1999:blog-3722233.post5848240539194877756..comments2018-11-20T15:58:48.801-05:00Comments on Computational Complexity: Math on TVLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-69897138394904243042007-09-22T22:30:00.000-04:002007-09-22T22:30:00.000-04:00As you can see, the perp mummified his victims so ...As you can see, the perp mummified his victims so they could not move or cry out. Twenty-seven of the bodies here belong to people already dead. To find the one living victim before we run out of time, we will use a breath-first search.Aaron Sterlingnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43226614865965211242007-09-22T02:39:00.000-04:002007-09-22T02:39:00.000-04:00Yeah, it'll be hard to beat Nisan-Wigderson derand...Yeah, it'll be hard to beat Nisan-Wigderson derandomization.<BR/><BR/>Here's my best attempt so far (but not as good as the derandomization one). You could have a vignette with some students leaving mathematics class saying:<BR/><BR/>Alice: Did you get any of that last proof? I was totally lost.<BR/>Bob: Yeah, it was a real zero-knowledge proof.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39257673768668967582007-09-21T12:54:00.000-04:002007-09-21T12:54:00.000-04:00Don: we screwed up - they know we don't know the e...Don: we screwed up - they know we don't know the exact amount.<BR/>Charlie: Don, let's plant a couple more false moves - that will give them a sense of security - but we know that we can apply Reed-Solomon error correcting to recover the correct sequence.<BR/>Amita: Do you think we'd need list-decoding?<BR/>Larry: Charles, are you sure their radius is within the Plotkin bound?<BR/><BR/>A bit lame, I know.<BR/>Bill, your "Nisan-Wigderson derandomization" is too cool - let's see if anyone can top that.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36519368351580111482007-09-21T11:55:00.000-04:002007-09-21T11:55:00.000-04:00I needed a proof of her love and she gave me, but ...I needed a proof of her love and she gave me, but unfortunately it was very long and complicated. I asked her if she could reformulate it as a PCP, so I would only have to look up three random bits, to be convinced. Sadly afterwards our relation has fallen to bits and pieces.<BR/><BR/>*not my math.Anonymousnoreply@blogger.com