if you haven't heard of sudoku yet, then you're at a big loss! it's such a fun game. the idea is that you're given a 9x9 grid like below. In each row, column, and square you must place the numbers 1 through 9. so that each number appears only once per row, column and square. It can be surpirsingly difficult! see the wikipedia here
at the theory lunch today, the speaker talked about sudoku from a theory perspective. here's the idea behind a zero knowledge proof. suppose alice wants to show bob that she has the solution to a given sudoku puzzle (there is only 1 solution) without revealing the solution itself. the act of doing this is called giving a zero-knowledge proof, because alice has given no knowledge about the actual solution BUT has shown that there is a solution, and she knows it. i won't go into the details on this one, but ask me if you're interested. (for you techies, sudoku is an NP-hard problem).
if you want to play now, go here
- ► 2008 (66)
- ► 2007 (72)
- ► 2006 (89)
- renting a place in the bay area
- [tech] the theory lunch and zero knowledge proofs
- this is my "office".. does it look clean from here...
- it's typical of the shelves in this room to contai...
- look closely above the notebook and to it's left. ...
- see all this stuff? no one actually seems to have ...
- the whiteboard in our office -- NOTE: this is AFTE...
- [tech] graphical models
- [tech] systems and databases -- oh my!
- the foundation series
- [tech] theory funding
- [tech] random algorithms, pleasant ideas
- [tech] and "normal" posts
- first day at school: day's end
- first day at school: midday
- first day at school: daybreak
- a place for my ideas and thoughts
- ▼ August (18)