CSC 591/791 - CS Theory Toolkit (Fall 2023)

Course information

Instructor: Chin Ho Lee (he/him) (chinho.lee@ncsu.edu)
Lectures: Tuesdays and Thursdays 10:15am-11:30am
Location: EB2 1226
Office hours: Tues 3-5pm @ EB2 3292, or by appointment
Readings: Perusall
Discussion: Ed
Homework submisson: HotCRP

Follow this Google calendar for the most updated schedule and events.
A syllabus can be found in this Google Doc.

Course Announcement

Course announcements are on Ed. Sign up here, or send me an email so that I can add you to the platform.

Course description

This course is intended to equip a student interested in studying theoretical computer science (TCS) with some of the fundamental tools commonly used in this area. We will study several mathematical tools and see how they are used to develop algorithms and prove impossibility results in various areas in computer science.

Evaluation

10% Scribe and class participation

10% Peer-reviewing (1 submission for each homework assignment)

60% Homework (6 problem sets)

20% Final exam (Take-home)

Textbook

Notes and references will be provided.

Lectures

Number	Date	Topics
1	8/22	Logistics, Topics preview
2	8/24	Load balancing: Union bound, Linearity of expectation, Binomial and Geometric distributions
3	8/29	Coupon collector, Factorials, Binomial coefficients
4	8/31	Birthday paradox, MinHash
5	9/5	MinHash, Sum of independent random variables
6	9/7	Empirical estimation, Chebyshev's inequality, higher moments
7	9/14	Chernoff's bound
8	9/21	MinHash
9	9/24	Fields and Polynomials, Prime number theorem
10	9/26	Communication complexity of EQ, Multivariate polynomials
11	10/3	Schwartz-Zippel lemma
12	10/5	Perfect Matchings in bipartite graphs, Error-correcting codes
13	10/12	Reed-Solomon Code, Singleton's bound
14	10/17	Dual codes, Hamming code, Hadamard code
15	10/19	Asymptotically good codes, Concatenated codes
16	10/24	Boolean funcions, Multilinear polynomial representation
17	10/26	Fourier basis, Parseval's identity, and other properties
18	10/31	Linear testing, BLR test
19	11/2	Spectral graph theory, undirected st-connectivity
20	11/7	random walk algorithm
21	11/9	eigenvalues and eigenvectors
22	11/14	graph spectrum
23	11/16	spectral gap of connected graphs
24	11/21	Expanders, spectral and vertex expansions
26	11/28	1-bit-probe data strcture for set membership
27	11/30	1-bit-probe data strcture for set membership
28	12/05	Entropy estimates of binomial coefficients

Homework and Exam

You are required to typeset your solution using LaTeX. Overleaf is a popular online LaTeX editor. For each problem set, you will also do some lightweight peer-grading.

Each student has 8 late days for homework submission throughout the semester, of which you can use up to 5 days on any problem set. Any extension beyond the 8 late days will be subject to Academic Absence Verification. When late days are used up and a problem set is submitted L days late, the grade for that problem set will be multiplied by 0.9^L.

You are allowed to discuss homework questions with others in the class, only after spending some time on them on your own. You must write down your own solutions, without consulting others while you are writing them.

You are not allowed to discuss the final exam with others and must work on the final exam on your own. There is no late day for final exam submission. There is no late day for final exam submission. Any extension request will be subject to Academic Absence Verification.