Selected Topics in Theory

0368-3247-01

[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.

Topics:

Error-Correcting-Codes

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

 

 

 

 

 

Assignments

Assignment #1: