Welcome to CS590 Sublinear Algorithms!
Algorithms that compute with a sublinear amount of resources
(time, space, communication) lie at the foundations of data science. They can
be used to analyze data across domains that span from social networks,
financial transactions, or genomic data, to satellite communications or
astronomical data. In this course we will study several sublinear models,
including the sublinear-time model of Property Testing, sublinear-space
streaming models, and sublinear-communication models. We will introduce many of
the combinatorial, algebraic and geometric techniques commonly used in
analyzing very fast algorithms for mathematical objects such as graphs,
strings, distributions, and error-correcting codes.
Prerequisites: A course on discrete math, undergraduate algorithms, and mathematical maturity.