In this course we will study how randomness helps in designing algorithms and how randomness can
be removed from algorithms.
We will start by formalizing computation in terms of algorithms and circuits. We will see an example
of randomized algorithms-- identity testing --and prove that eliminating randomness would require
proving hardness results. We prove hardness results for the problems of parity and clique using
randomized methods. We construct `highly’-connected graphs called expanders that are useful in
reducing randomness in algorithms. These lead to a surprising logarithmic-space algorithm for
checking connectivity in graphs. We show that if there is hardness in nature then randomness cannot
exist! This we prove by developing pseudo-random generators and error-correcting codes.
INTENDED AUDIENCE : Computer Science & Engineering, Mathematics, Electronics,
Physics, & similar disciplines.
PRE REQUISITE : Preferable (but not necessary) - Theory of Computation, or
Algorithms, or Discrete Mathematics
INDUSTRY SUPPORT : Discrete Optimization, Cryptography, Coding theory, Computer
Algebra, Symbolic Computing Software, Cyber Security,Learning Software