#
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
undergraduate students.

Topics include:

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
Embeddings
Problems arising from linear programing