COSC 547 - Analytic Methods in Computer Science

Reiss 559

Georgetown University

Prof. Justin Thaler

Monday and Wednesday, 2:00pm to 3:15pm

Email: justin.thaler at georgetown dot edu

Course Overview

Description

Analytic techniques have become influential in many areas of theoretical computer science. This course will survey some of the most broadly applicable of these techniques and their most important applications. Techniques to be covered include discrete Fourier analysis and approximation theory. Application domains include PAC learning, quantum computing, and communication complexity.

Prerequisites

There are no formal prerequisites for this course. However, substantial mathematical maturity will be expected, as will knowledge of basic probability theory, induction, asymptotic notation, modular arithmetic, and the notion of NP-completeness (these topics will be reviewed in lecture, but quickly). If you have not previously taken an algorithms or theory of computation course, you will likely be unprepared.

Reference Material

The course reference is a draft monograph written by the instructor that is available on Canvas.

Grading

Grades in the course will be based on participation (comments on the reading), problem sets, and a final project. Each component will count for 1/3 of the grade. Information about the final project will be provided later in the semester.

Academic Honesty

Academic honesty is taken very seriously, in accordance with Georgetown's Honor System. For problem sets, you are welcome to work with others or use other resources, but when you actually write your solutions you must do so by yourself as if you are taking an exam. You must also explicitly list all collaborators with whom you worked and any references or online material you used, separately for each problem. Most importantly, you must never turn in something that you do not understand. I reserve the right to ask you to explain to me something that you turned in; if you cannot do so in a way that demonstrates your understanding, then you will receive no credit and possibly be reported to the Honor Council.

Lateness Policy for Problem Sets

Problem sets not submitted until the day after the deadline will have an additional 10% deducted. Beyond this point, problem sets will not be accepted.

Course Logistics

Office Hours

After class or by appointment.

Title IX: Sexual Misconduct and Sexual Harassment

Georgetown University and its faculty are committed to supporting survivors of sexual misconduct, including relationship violence and sexual assault. Please note that university policy requires faculty members to report any disclosures about sexual misconduct to the Title IX Coordinator, whose role is to coordinate the University’s response to sexual misconduct. For details of University resources, consult Georgetown University's Sexual Misconduct Reference Guide.

Schedule

Below is the highly tentative schedule for the course. I will modify it as the semester progresses. Topics and readings will not become "official" until the date of lecture.

Class Number	Date	Description	Readings
1	8/24	Course overview; introduction to approximate degree and its applications: quantum computing, query complexity, communication complexity	No reading.
2	8/29	Fourier Analysis of Boolean Functions	Section 1 of Bun and Thaler. Sections 1.1 - 1.4 of Analysis of Boolean Functions by Ryan O'Donnell
3	8/31	Introduction to Approximate Degree. Upper bound for OR.	Section 2 of Bun and Thaler
4	9/6	Lower bound for OR.	Sections 3.1-3.3 of Bun and Thaler
5	9/7	Introduction to query complexity. The polynomial method in query complexity. Error reduction for randomized query complexity and approximate degree.	Sections 5.0 and 5.1 of Bun and Thaler
6	9/12	Approximate degree of symmetric functions. Threshold degree lower bound for Parity.	Section 4.1 of Bun and Thaler, followed by Sections 3.4 and 3.5. Optional reading: Section 3 of Buhrman and de Wolf's survey on query complexity and related topics
7	9/14	Threshold degree upper and lower bounds for the Minsky-Papert CNF	Section 5.3 of Bun and Thaler
8	9/19	Application: PAC learning	Begin Section 11.2 of Bun and Thaler
9	9/21	Application: Agnostic learning	Finish Section 11.2 of Bun and Thaler
10	9/26	Introduction to linear programming and duality	Section 12.1 of Vazarani's book
11	9/28	The method of dual polynomials for lower bounding approximate degree	Section 6.0 of Bun and Thaler
12	10/3	Application: Secret sharing schemes via dual polynomials	Section 11.1 of Bun and Thaler
N/A	10/5	Dual block composition, approximate degree lower bound for the AND-OR tree	Sections 7.0 and 7.1 of Bun and Thaler
13	10/10	Campus holiday, no class	No reading
14	10/12	Hardness amplification results via dual block composition	Section 7.2 of Bun and Thaler
15	10/17	Introduction to communication complexity	Section 10.2 of Bun and Thaler
16	10/19	Query-to-communication lifting theorems	Sections 10.0, 10.1, and 10.3 of Bun and Thaler
17	10/24	Begin the pattern matrix method for communication lower bounds	Sections 10.4.0-10.4.1 of Bun and Thaler
18	10/31	Finish the pattern matrix method for communication lower bounds	Sections 10.4.0-10.4.2 of Bun and Thaler
19	11/2	Applications in communication and circuit complexity, Part 1	Reading TBD
20	11/7	Applications in communication and circuit complexity, Part 2	Reading TBD
21	11/9	Applications in communication and circuit complexity, Part 3	Reading TBD