**Algebraic Gems in Discrete Mathematics and Theoretical
Computer Science**

**16.642.587 Selected Topics in Discrete
Mathematics**

**Instructor:**
Shubhangi Saraf

**Email:** shubhangi.saraf@rutgers.edu

**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

projections

· Introduction to arithmetic
circuits/arithmetic computation, polynomial factorization

and polynomial identity testing