[tech] random algorithms, pleasant ideas

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.