כלים בסיסיים בדרנדומיזציה: גרפים מרחיבים, מזקקים וקודים מתקני שגיאות
Basic Tools in Derandomization: Expanders, Extrsctors and Error Correcting Codes
In this course we study three basic tools used in theoretical computer science and elsewhere: Extractors, Error correcting codes and Expanders. We will study both the combinatorial existence problem, and the computational challenge of coming up with explicit constructions. We will also study the many fundamental connections between these seemingly different objects
There will be about five homework assignments, each with several theoretical questions and one programming question asking to actually implement an algorithm or a fundamental ideas presented at class. In addition there will be one take-home exam at the end of the course.
The grade is 50 \% the take home exam, 40 \% for the HW assignments and 10 \% for participation in class.