Randomized Methods in Computational Complexity

Lecturer - Prof. Nitin Saxena

1. Introduction

2. Polynomial Identity Testing and Circuits

3. Derandomization and lower bounds

4. Constant depth circuits are weak

5. Monotone circuits are weak

6. Expansion properties

7. Explicit expander constructions

8. Pseudorandom Generators

9. Error-correcting codes amplify hardness