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