18.204 Seminar in Discrete Math | Fall 2026

Instructor: Margalit Glasgow (mglasgow@mit.edu)

Communication Specialist: Matthew Halm (halm@mit.edu)

Class Schedule: Tuesday and Thursday 11:00am-12:30pm in 56-162

Syllabus: here

Office Hours: 4-5pm Monday, room 26-142, 4:30-6 Wednesday in room 26-139. Please email me if you plan to come to attend Wednesday, as we may have practice presentations some of the time. You may also email me to make an appointment for another time to meet.

Course Goals and Description In a seminar, mathematicians help each other to learn a body of material. The main object of this undergraduate seminar is for you to help each other learn about combinatorial learning theory, while simultaneously helping each other to better present, discuss, write, and read mathematics. To this end, you will take turns collaboratively presenting sections from a textbook or research papers to each other, and you will also write a 10-page expository paper on a topic of your choice. Topics include classical ideas such as:

• PAC Learning and the VC dimension

• Online Learning and the Littlestone dimension

• Differentially Private Learning

• Boosting

... along with more recent research papers in the field.

The main course deliverables will be:

1. A 40-minute chalkboard presentenation based on textbook or course notes material. You must meet with me to get feedback on your presentation before presenting.

2. A 40-minute slide presentation on material from a research paper.

3. A 20-minute presentation (slides or chalkboard) on the topic of your final paper.

4. A 10-page expository paper on a topic of your choice. This will be completed in stages. You will propose a topic or choose one from the provided list here, write a partial draft for feedback from me, complete the paper, submit it for feedback from peers, critique the drafts of two of your classmates, and submit the final version of the paper. The paper does not need to contain original work, but the writing must be your own and all sources must be properly acknowledged. The paper must be written in the style of a research or expository journal article and must be about 10 pages long.

5. Five small problem sets based on the course material. These are to ensure you understand the material (especially in the first few weeks of the class) as it builds on itself.

Textbook and Material We will follow some chapters from Understanding Maching Learning by Shalev-Shwartz and Ben-David. Further materials will be given in the course schedule. The full course schedule is available here, including the schedule of assignments. Sign up for presentations here. All sources are available freely online.

Prerequisites The formal prerequisites are ((6.1200 or 18.200) and (18.06, 18.700, or 18.701)), and it is important that you have a solid understanding of discrete probability. You should be comfortable with tail bounds (Markov, Chebychev, Chernoff bounds); see for example Ankur Moitra's notes here.

Since the topics of this course will build upon eachother, it will be essential to stay on top of the material throughout the semester.

Class Participation Roles and Feedback In addition to attending class, you will be expected to actively engage in class discussion. To encourage participation, students will be assigned the roles such as the following (expect to perform a role once every few classes):

1. Scribe: take and type up notes from the class presentation.

2. Designated novice: Ask at least once about a step that could benefit from more explanation.

3. Nit-picker: Point out any notation or mathematical errors (focus on ones that can be confusing).

4. Hypothesis tester: Pick one interesting way to weaken the assumption of a result presented. Try to figure out if/how the result breaks, and show a counterexample if possible. Share your finding or ask for the presenter or class's thoughts at the end of the presentation.

5. Example generator: Find a simple example demonstrating the main result.

Additionally, everyone will be expected to give feedback at the end of each class session, using the feedback form.

Grading

1. 50% talks. (20%, 20%, 10% for each talk). Rubric for the first talk.

2. 15% attendance, participation roles, and feedback to presenters

3. 10% problem sets (2% / pset)

4. 25% final paper, including drafts and peer critique (2% proposal, 5% partial draft, 5% complete draft, 3% peer critique, 10% final draft)

Late Submission Policy Late problem sets will not be accepted. However, your lowest problem set grade will be dropped.

AI Usage Policy The goal of this course if for you to learn to plan and execute a presentation, and to write an academic-style paper. If you delegate those tasks to AI, you will not learn them yourself.You may use AI to help you understand the content of the sources of your presentation or paper, and to choose topics and sources for you final paper. AI may NOT be used to write any part of the presentation or paper itself. The exception is for generating figures or formatting. Any use of AI should be stated in the acknowledgements section of the paper or at the end of the presentation.

The problems sets will be useful to check and bolster your understanding of the course material, which builds on itself. Thus I encourage you to try to solve the problems independently or with your peers, though you may use AI for brainstorming. Attach to your pset the prompts and outputs you gave to AI, along with a note on how you used them.

If you are unsure if a use of AI is acceptable, please consult with me. Misuse of AI, including direct copying, will be considered academic dishonesty.