|
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.
|
|
הטכניון - מכון טכנולוגי לישראל Technion - Israel Institute of Technology Технион - израильский технологический институт ألتخنيون - معهد تكنولوجي لإسرائيل