Lecture 1: Course overview , codes, linear codes.

Week 2: Concentration of measure, Linear Codes: Random, Reed - Solomon, Reed - Muller, Hadamard. Concatenation of Codes.

HW1

Lecture 3: Boolean functions: fourier representaiton, Plancherel/Parseval, influences, linearity test(BLR), average sensetivity, noise operator.

HW2

Lecture 4: Hypercube graph, isoperimetric meaning, long code, long code test, gap problems. KKL and Friedgut theorems(statements), tribes function. Noise operator, stability.

Lecture 5: Theorems of Friedgut, Bourgain, MOO. Russo's lemma, Stability of majority. Bonami - Beckner inequality.

HW3

Lecture 6: Random restrictions, Finding heavy coefficients - Kushilevitz Mansour's algorithm. Proof of Friedgut's theorem, Entropy conjecture.

Lecture 7: One way functions, Hardcore predicates, Goldreich - Levin's hardcore predicate, FKN theorem

HW4

Lecture 8-9: Geomans - Williamson algorithm for max-cut, gap problems, gap preserving reductions, UG conjecture, UG hardness for max-cut SDP

Lecture 10: Constraint satisfaction graphs, gap amlification, hardness of approximating IS, proof of the UG hardness of max-cut

Lecture 11: Lattices: the dual lattice, SVP, CVP. Basing encryptions on lattice problems(Ajtai-Dwork). LLL reduced bases, LLL algorithm. Lattices

Lecture 12: Gap versions of SVP, CVP. Reduction from gap-CVP to gap-SVP(Micciancio).Analysis of LLL algorithm.

HW5

Lecture 13: More on CVP' to SVP reduction. Testing juntas(tester of Blais, analysis of Blais, Weinstein Yoshida)