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


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.


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.


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.


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 NumberDateDescription Readings
18/24Course overview; introduction to approximate degree and its applications: quantum computing, query complexity, communication complexity No reading.
28/29Fourier Analysis of Boolean Functions Section 1 of Bun and Thaler. Sections 1.1 - 1.4 of Analysis of Boolean Functions by Ryan O'Donnell
38/31Introduction to Approximate Degree. Upper bound for OR. Section 2 of Bun and Thaler
49/6Lower bound for OR. Sections 3.1-3.3 of Bun and Thaler
59/7Introduction 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
69/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
79/14 Threshold degree upper and lower bounds for the Minsky-Papert CNF Section 5.3 of Bun and Thaler
89/19 Application: PAC learning Begin Section 11.2 of Bun and Thaler
99/21 Application: Agnostic learning Finish Section 11.2 of Bun and Thaler
109/26 Introduction to linear programming and duality Section 12.1 of Vazarani's book
119/28 The method of dual polynomials for lower bounding approximate degree Section 6.0 of Bun and Thaler
1210/3 Application: Secret sharing schemes via dual polynomials Section 11.1 of Bun and Thaler
N/A10/5 Dual block composition, approximate degree lower bound for the AND-OR tree Sections 7.0 and 7.1 of Bun and Thaler
1310/10 Campus holiday, no class No reading
1410/12 Hardness amplification results via dual block composition Section 7.2 of Bun and Thaler
1510/17 Introduction to communication complexity Section 10.2 of Bun and Thaler
1610/19 Query-to-communication lifting theorems Sections 10.0, 10.1, and 10.3 of Bun and Thaler
1710/24 Begin the pattern matrix method for communication lower bounds Sections 10.4.0-10.4.1 of Bun and Thaler
1810/31 Finish the pattern matrix method for communication lower bounds Sections 10.4.0-10.4.2 of Bun and Thaler
1911/2 Applications in communication and circuit complexity, Part 1 Reading TBD
2011/7 Applications in communication and circuit complexity, Part 2 Reading TBD
2111/9 Applications in communication and circuit complexity, Part 3 Reading TBD