Course No.: MATH 945 / CS 945
Topic in discrete mathematics:
Mathematical problems arising from theoretical computer science
Instructor: Gil Kalai
Schedule (NOTE CHANGE IN TIME) : MW 11:30-12:45
Important Notice: Change in Times The last week of September
and the first week of October
The week starting November 6
No class on Novenber 6, Class as ususal November 8 Class on THURSDAY November 9
meeting: 11:30 AKW 400.
First class Thursday, September 7: 1:00 the same material repeated
on Monday Sept 11, 11:30.
Location: (NOTE CHANGE IN PLACE) AKW 400
September 7 and September 11
Sum product theorems and application I.
If A is a set of n positive reals then the set A+A of pairwise sums
of elements of A has at least 2n-1 elements. (Equality for arithmetic
progression.) The same is true for the set (A times A) of pairwise products.
Erdos conjectured that either A+A or (A times A) have quadratic size.
We prove a theorem of Elekes that at least one of them has size > n**(5/4).
The proof is a nice tour from combinatorial number theory to combinatorial
geometry and back.
Product-sum theorems played important role recently in theoretical computer
science and mathematics. We will come back to them.
September 13 and September 18 and September 20
Some basic results from extremal set theory.
We will state and prove several basic results of extremal set theory:
Erdos-Ko-Rado Thm, Sauer-Shelah Thm,
Harris-Kleitman Inequality (baby FKG) and applications,
Sperner Theorem, Ramsey Theorem.
September 27 and September 29
Evasiveness. A nice application of algebraic topology to
decision trees complexity.
Evasiveness, decision tree complexity, through mid October.
Collective coin flipping and
analysis of Boolean function, through the first week of November.
A brief description of the course:
We will study a variety of mathematical problems
arising from theoretical CS and mathematical method
used in theoretical CS.
This is a graduate course and it is open also to advanced
Sum product theorems and applications
Basic theorems of extremal combinatorics
Decision trees, evasiveness and algebraic topology
Randomness and explicit constructions
Spectral methods and expanders
Boolean functions and their analysis
VC dimension and learning
Some applications of entropy
Problems arising from linear programing