Abstract
There are two way randomness enters analysis of Big Data: either the input data or the algorithm may "toss coins" (or even both). The former involves stochastic models of data. The idea in theory is to get provable algorithms which work in the worst case under such models. The talk will recap mixture models, their use in clustering, planted dense graphs, and other problems and algorithms that work under the model. Coin tossing by the algorithm will be touched upon depending on the coverage of this topic in other lectures.