Randomized Methods in Complexity
Offered By: Indian Institute of Technology Kanpur via Swayam
Course Description
Overview
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
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
Syllabus
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.Taught by
Prof. Nitin Saxena
Tags
Related Courses
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie ChenInstitute for Advanced Study via YouTube Expander Graph Application 2: Derandomization - Lecture 16c of CS Theory Toolkit
Ryan O'Donnell via YouTube Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
Association for Computing Machinery (ACM) via YouTube High-Precision Estimation of Random Walks in Small Space
IEEE via YouTube Nearly Optimal Pseudorandomness From Hardness
IEEE via YouTube