Randomized Methods in Complexity

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 MathematicsINDUSTRY SUPPORT : Discrete Optimization, Cryptography, Coding theory, Computer Algebra, Symbolic Computing Software, Cyber Security,Learning Software

COURSE LAYOUT

Week 1: Outline. Introduction to Complexity.Week 2: Circuits. Polynomial Identity Testing (PIT).Week 3: Derandomize & get a lower bound.Week 4: Constant-depth circuits are weak.Week 5: Monotone circuits are weak.Week 6: Random Walk converges fast.Week 7: Expansion properties.Week 8: Construct Explicit Expanders.Week 9: Pseudorandom generator (prg) & hardness.Week 10: Error-correcting codes.Week 11: List Decoding. Local List Decoding.Week 12: Error-correcting codes amplify hardness.