- The list of suspects looks random but we know that its not. To solve the case we use the Nisan-Wigderson derandomization technique.
- We know the murder took place within this 5 block by 5 block area. We know that there were 10 people interacting to plan it. We can solve the case by looking at both the space and the interactions and then applying the Lund-Fortnow-Karloff-Nisan theorem that changes space into interactions.
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Friday, September 21, 2007
Math on TV
There was an episode of NUMB3RS (which starts its fourth season next Friday) that mentioned the the Kruskal Count (See also this link) This is a card trick invented by Martin Kruskal. His son Clyde Kruskal is in my dept. Martin passed away in late December of 2006 and it is likely they put that reference in as a tribute. (See this and this for comments on the memorial service.) I watched the episode with Clyde. The good news is that YES, they did indeed mention The Kruskal Count and thats kind of cool seeing someone you know mentioned on NUMB3RS. The bad news is that the reference made no sense whatsoever. Here are two items that make as much sense as what they said.
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.ReplyDelete
*not my math.
Don: we screwed up - they know we don't know the exact amount.ReplyDelete
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.
Amita: Do you think we'd need list-decoding?
Larry: Charles, are you sure their radius is within the Plotkin bound?
A bit lame, I know.
Bill, your "Nisan-Wigderson derandomization" is too cool - let's see if anyone can top that.
Yeah, it'll be hard to beat Nisan-Wigderson derandomization.ReplyDelete
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:
Alice: Did you get any of that last proof? I was totally lost.
Bob: Yeah, it was a real zero-knowledge proof.
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.ReplyDelete