Course Identification

Title:

A theorist's toolkit

Code:

20184212

Lecturers and Teaching Assistants

Lecturers:

Prof. Irit Dinur

TA's:

Dr. Karthik Srikanta

Course Schedule and Location

Year:

2018

Semester:

Second Semester

When / Where:

Sunday, 14:15 - 16:00, Jacob Ziskind Building, Rm 155

First Lecture:

18/03/2018

Field of Study, Course Type and Credit Points

Mathematics and Computer Science: Lecture; Elective; 2.00 points

Comments

N/A

Prerequisites

No

Restrictions

Participants:

50

Language of Instruction

English

Attendance and participation

Expected and Recommended

Grade Type

Numerical (out of 100)

Grade Breakdown (in %)

Attendance

30%

Assignments:

30%

Final:

40%

Evaluation Type

Final assignment

Scheduled date 1

Date / due date

N/A

Location

N/A

Time

-

Remarks

N/A

Estimated Weekly Independent Workload (in hours)

2

Syllabus

a theorist's toolkit

This course will cover a variety of mathematical topics that come in handy for theoretical computer science. It is intended mainly for students earlier in their graduate studies who might want to do theory research. The idea for the course comes from other courses by Arora (2002, 2007), Håstad (2004/05), Kelner (2007, 2009), and Tulsiani (2013), and O'Donnell (2016)

Topics will include

* spectral graph theory: Rayleigh quotients, Expander graphs, Cheeger's inequality

* probability: tail inequalities, Markov chains

* analysis of Boolean functions: Fourier analysis, influences, hyper-contractivity

Additional topics may be

* Polynomials over finite fields and applications to coding theory

* Cayley graphs and groups

Additional topics may vary depending on student interest

Learning Outcomes

Upon successful completion of the course, the student will be able to:

Be comfortable with mathematical tools that are often used in theoretical computer science. In particular: Spectral analysis of graphs, and Fourier analysis for Boolean functions.

Reading List

N/A

Website

N/A