Selected Topics in Theory


[Wdnesday 12-3pm, Schreiber 00?]


Prerequisite Course: Complexity Theory (undergraduate)

Instructor: Muli Safra

The course covers selected topics in Theory of Computer Science. Here is a partial/non-final list.



Harmonic Analysis of Boolean functions

Local-Testing of Hadamard Code

Expander graphs: Measure of Expansion, Mixing time

Learning of Concentrated functions --- over Binary group and on a general Abelian group

Advanced Analysis assertions: Entropy; Influence and Noise Sensitivity; Juntas

Embedding: Distortion upper and lower bounds


Lattice problems


Lecture Notes







Assignment #1: