**Lectures**Wed 11:30-2:15 in ERB 804**Instructor**Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, SHB 926**Office hours**Fri 10.30-12.30 (or by appointment)

**Apr 23**The presentation on Wednesday will be in the usual classroom (ERB 804). Please try to finish your presentation in 15 minutes.**Apr 16**In problem 1 of homework 3 assume that*f*is balanced (E[*f*(*x*)] = 1/2), otherwise part (b) is not true. I also fixed an issue in problem 3.**Apr 11**Homework 3 is due on Wed Apr 25 in class.

This course will cover tools and techniques that have proven useful in the theory of computing over the years. They have contributed to advances in many areas inside and outside theory, like learning, cryptography, and optimization. These techniques often originate from distant fields like algebra, signals, and information theory. They found their way into computer science through the effort of passionate graduate students like you, who dazzled the world by mastering them applying them towards solving hitherto intractable problems. It is time for you to continue this tradition!

Regardless of your area of expertise (it doesn't have to be theory), try this course, become more confident in your technical skills, go forth, and make a splash.

This is a tentative plan for the topics to be covered this semester. Changes are possible and you are welcome to suggest other things you would like to see in the class.

date | topic | reading | |
---|---|---|---|

1 | Jan 11 |
Coding theory Rate and distance, Reed-Solomon and BCH codes, bounded independence. |
[pdf] |

2 | Jan 18 |
The Gilbert-Varshamov bound, concatenation, small-bias sets. | [pdf] |

Jan 25 |
No class, Year of the Dragon | ||

3 | Feb 1 |
Decoding and list-decoding. Secret sharing from codes. | [pdf] |

4 | Feb 8 |
Local decoding. Reed-Muller codes. Relations between worst-case and average-case hardness. | [pdf] |

5 | Feb 15 |
Analysis of boolean functions Fourier decomposition. The Kushilevitz-Mansour algorithm. |
[pdf] |

6 | Feb 22 |
The Fourier spectrum of shallow circuits. | [pdf] |

7 | Feb 29 |
Gowers uniformity and low-degree testing. | [pdf] |

8 | Mar 7 |
Fourier analysis, small-biased sets, and pseudorandomness. | [pdf] |

9 | Mar 14 |
Hardness of approximation for some constraint satisfaction problems. | [pdf] |

Mar 21 |
No class | ||

10 | Mar 28 |
Expanders Eigenvalues, random walks, and an application to hardness of approximation. |
[pdf] |

Apr 4 |
No class, Ching Ming Festival | ||

11 | Apr 11 |
Cayley graphs and Kazhdan constants. The Margulis-Gabber-Galil expander. | [pdf] |

12 | Apr 18 |
Two applications of expanders to small-biased sets. | [pdf] |

Apr 25 |
Project presentations |

**Prerequisites**There are no formal prerequisites for this class, but it helps to be comfortable with discrete mathematics and probability.**Grading and homeworks**Your grade will be determined from homeworks (30%), a take-home midterm exam (30%), and a final project (40%). Three homeworks will be issued throughout the semester. You are encouraged to collaborate on the homeworks as long as you write up your own solutions.**Final project**For your final project you will be expected to do some independent reading, a presentation in class, and a short report. A list of suggested projects and more details will be provided around the middle of the semester.

Notes will be provided for every lecture. There is no required textbook. Links to other material may also be provided for some lectures. The following materials may give you an idea about some of the topics:

- Venkat Guruswami: Introduction to coding theory.
- Ryan O'Donnell: Analysis of boolean functions.
- Shlomo Hoory, Nati Linian, Avi Wigderson: Expander graphs and their applications [pdf].