ألتخنيون - معهد تكنولوجي لإسرائيل
		236605 - Advanced Topics in Computer Science 5
		شتاء 2009-2008
	مادة الدورة Lectures Covered in Lecture 1 In the first lecture we saw some applications to inclusion matrices - Lindstrom's theorem - Even town, Odd town - Fisher Inequality - Nagy's construction of a Ramsey Graph Covered in Lecture 2 At the second lecture we met the role of eigenvalues in the study of graphs. - Hoffman-Singleton theorem (If a regular graph of degree d and girth 5 has 1+d^2 vertices then d is 2,3,7 or 57). - Introduction to expanders. Covered in Lecture 3 At the third lecture we saw three inequalities regarding Expanders. We also started to look at a construction of error correcting codes based on Expanders, due to Sipser and Spielman. Covered in Lecture 4 At the fourth lecture we proved the result of Sipser and Spielman, and briefly mentioned other results on expander graphs. Covered in Lecture 5 The Polynomial Method has been introduced. We saw Graham-Pollack theorem Points with only 2 distances Frankl-Wilson Theorem Ramsey Graph from F-W Theorem Covered in Lecture 6 In the sixth lecture we've disproved Borsuk's Conjecture and started to talk on Combinatorial Nullstellenatz Covered in Lecture 7 After a reminder on Combinatorial Nullstellensatz, we've witnessed some applications: - Cauchy-Davenport theorem - Chevalley-Warning theorem - The Permanent lemma Covered in Lecture 8 We turn to see some uses of polynomials for lower bounds on circuits. Covered in Lecture 9 - We saw the use of partial derivatives for proving the following result: any boolean function is of low degree over only at most one prime field. - Morgenstern's lower bound for computing DFT with bounded coefficients. Covered in Lecture 10 In the tenth lecture we sae - The use of partial derivatives as a complexity measure. - Polynomial identity testing. Covered in Lecture 11 We saw application of the algebraic method to geometry. Specially, we looked at the moment curve. Recitations Recitation 1 Reminder on some of the algebraic tools we'll need in the course. Recitation 2 Classic results from extremal set theory Recitation 3 Walk on Expanders Recitations 4,5 Explicit construction of constant degree Expanders Recitation 6 The Chromatic number of R^n Recitations 7,8 (on the same day) On the size of Kakeya sets over finite fields. Recitation 9 Combinatorial Nullstellensatz application to the List Coloring problem. Recitation 10 Reed Solomon codes Recitation 11 Reed Solomon list decoding Recitation 12 Introduction to Analysis of Boolean Functions. Based on Ryan O'Donnell's presentation. Recitation 13 Linearity and the Fourier Expansion - The BLR Test Recitations 14,15 Proof of the LMN Lemma.