my first class today was random computation. essentially it's about adding random bits as an input to the turing machine model, and seeing what we can do. i've had some background in random algorithms before, and so i feel pretty prepared. in addition, it was really pleasing to be faced with a Problem, an Input, and a Solution. Life doesn't work that way, but the nice world of random algorithms does.
We talked about a bunch of problems in random algorithms, but the most interesting problem, that i don't expect to solve given that so many people haven't, is the problem of determining whether, for every randomized algorithm, is there a deterministic algorithm that does just as well in run-time and solves basically the same problem. essentially the question is whether the random bits actually add anything to the model, making it more powerful.
- ► 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)