randomness is a resource which can be used. Our unit of computation is a randomized turing machine some questions of randomness save time/space by using randomness: we used to believe that P \subset \text{Randomized } P, L \subset \text{Randomized } L, etc. But we now think P = \text{Randomized } P (intuition: if solving SAT requires circuits of exponential size, then P is equal to Randomized P). efficient derandomized: can we reduce usage of randomization—i.e. completely derandomize it while not loosing a lot of efficiency? properties of random algorithms they… have error: not super bad, since we can bound their error—repeating a randomized algorithm k times yields 2^{-\Omega\left(k\right)} factor error. hard to obtain: very hard to get true randomness; in practice we use pesudorandomness examples of random algorithms matrix multiplication verification \begin{equation} \left{\langle A, B,C\rangle : AB = c\right} \end{equation} we can do this in O\left(n^{2}\right) with randomness, in particular by sampling a v and checking if AB v = Cv minimum spanning tree see minimum spanning tree for G with n nodes and m edges, randomized algorithm gives a result in O\left(m\right), by Karger-Klein-Tarjan. undirected STCONN this is randomized O\left(\log n\right) space (because we can just take an O\left(n^{3}\right) random walk and wait til you reach t from s). (actually this is secretly deterministic O\left(\log n\right) space thanks to Omer). The reason why we need to take at most O\left(n^{3}\right) steps because the maximum number of steps starting from a particular node to visit all nodes is O\left(n \cdot m\right) for n nodes in the graph and m (at most O\left(n^{2}\right)) edges (“for every node, pick a next edge”). PERFECT-MATCHING See PERFECT-MATCHING polynomial identity testing given f\left(x\right), check if f\left(x\right) is identically 0.