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