Algebraic Gems in Discrete Mathematics and Theoretical Computer Science
16.642.587 Selected Topics in Discrete Mathematics
Instructor: Shubhangi Saraf
Timing: Mon, Wed 3:20 – 4:40 pm
Location: HILL 005
Office hours: Wed 1:30 pm – 2:30 pm (Hill 426)
Prerequisites: Basic combinatorics, basic linear algebra, mathematical maturity
Description: In the last few decades, algebraic methods have proven to be extremely
powerful in several areas of discrete mathematics and theoretical computer science. Many of the
recent and important advances in the field have relied on very simple
properties of polynomials. In this course we will see many interesting
and often surprising applications of linear algebra and polynomials to
combinatorics, discrete geometry, algorithm design, error correcting codes and complexity theory.
We will develop all the algebraic tools that we need along the way.
No background in algebra will be necessary. However it might be
helpful to have some familiarity with discrete math/algorithms and
linear algebra. The only real prerequisite is some mathematical
maturity. Students with an interest in discrete mathematics and/or
theoretical computer science are welcome.
A tentative list of topics that will be covered:
. The polynomial method with applications to Kakeya sets, Joints conjecture,
Erdos distinct distances problem, problems in incidence geometry and the recent breakthrough works on capsets.
· Polynomials in the design and analysis of error correcting
codes and other combinatorial structures
· Applications of linear algebra: eigenvalues and expansion in
graphs, applications of dimension and rank arguments, random
· Introduction to arithmetic circuits/arithmetic computation, polynomial factorization
and polynomial identity testing