Fall 2024, Brown University
Course Syllabus
See here; this mostly summarizes this webpage
Time and Location
Tuesday, Thursday, 9:00AM – 10:20AM, location TBD
Instructor
Ellis Hershkowitz, CIT 507
Office Hours
TBD
Teaching Assistants
Richard Huang
Jay Sarva
Doing research in theory and algorithms is often inaccessible because it requires an eclectic mathematical toolkit that is spread over many areas. The goal of this course is to consolidate many of these tools into a single course. Namely, this course will equip students with a mathematical foundation that will allow them to jumpstart their own theory research, particularly in algorithms. The course will cover not only many of the recurring mathematical tools in algorithms but also the ways in which these tools are used to design algorithms with rigorous guarantees. It is intended mainly for early-stage theory graduate students and advanced undergraduates. Some planned topics include polyhedral methods, metric embeddings, techniques from graph theory and the multiplicative weights framework.
Prerequisites:
The only official pre-requisite for the class is CSCI1570.
That said, you should be “mathematically mature” and have a strong background with formal proofs. Ideally, you have some background in and comfort with proof-based algorithm design and analysis. You will also have to know the basics of probability, NP-completeness, linear algebra and calculus.
If you’re unsure if you have an appropriate background feel free to reach out and we can discuss!
The class is broken into 7 sections as below.
Basic Tools | |
Sep 5 (Thurs) | Overview of Class + Learning, Doing and Writing Theory |
Sep 10 (Tues) | Asymptotics |
Sep 12 (Thurs) | Common Inequalities |
Sep 17 (Tues) | Common Proof Strategies |
Randomized Algorithms | |
Sep 19 (Thurs) | Common Randomization Paradigms |
Sep 24 (Tues) | Concentration |
Sep 26 (Thurs) | Union Bounds and How to Beat Them |
Polyhedral Methods | |
Oct 1 (Tues) | LP Basics |
Oct 3 (Thurs) | Duality (+ Complementary Slackness) |
Oct 8 (Tues) | LP Algorithms: Ellipsoid and Separation |
Oct 10 (Thurs) | Using LPs: Randomized Rounding+Primal-Dual |
Oct 15 (Thurs) | Using LPs: Iterative Rounding (+ Rank Lemma) |
Oct 17 (Tues) | Using LPs: Submodular Function Minimization |
Geometry and Metric Embeddings | |
Oct 22 (Tues) | Intro to Metrics and Bourgain’s Embedding |
Oct 24 (Thurs) | LSH and Dynamic ANN |
Oct 29 (Tues) | Random Projections and Johnson-Lindenstrauss |
Cuts and Flows | |
Oct 31 (Thurs) | Karger’s Min-Cut Algorithm |
Nov 5 (Tues) | No Class, Election Day |
Nov 7 (Thurs) | Multi-Commodity Flow-Cut Gap and Sparsest Cut |
Nov 12 (Tues) | Expanders and Expander Decompositions |
Graph Sparsification | |
Nov 14 (Thurs) | Distance Sparsification: Spanners |
Nov 19 (Tues) | Cut Sparsification: Gomory-Hu Trees (+ Uncrossing) |
Nov 21 (Thurs) | Distance Sparsification: LDDs and Tree Embeddings |
Nov 26 (Tues) | Flow Sparsification: Oblivious Routing via Raecke Trees |
Nov 28 (Thurs) | No Class, Thanksgiving Break |
Multiplicative Weights | |
Dec 3 (Tues) | The Experts Framing |
Dec 5 (Thurs) | Fast Multi-Commodity Flow |
Dec 10 (Tues) | Online Set Cover |
Dec 12 (Thurs) | TBD |
The homeworks will be posted here.
The exams will be posted here.
Students in the course will be responsible for the following:
The breakdown of grades is as follows:
with the usual grade assignments (an A is 90% or higher, a B is 80% or higher and not an A etc.). Note the >100% sum above. I may also curve (upwards) depending on averages.
Here are some additional resources that you may find useful.
Similar Classess
Some Links About Doing Theory/Math:
Here are some more general links to both talks and blog-post-type writings of various theoreticians and mathematicians that you might find useful.
If you feel you have a disability that could affect your performance in the course, please contact SAS and ask them to contact me. I’ll do whatever I can to support recommended accommodations.
Doing theory is extremely difficult if you aren’t feeling physically and mentally well, included and supported by your peers and mentors or otherwise marginalized.
My hope is that this is a welcoming and inclusive course. If you feel you have been mistreated please feel free to contact me directly or consider reaching out to some of the student advocates in the department. If you feel you might be the victim of harassment, consider reaching out to the Brown Title IX Office.
If you feel you are overstretched or otherwise psychologically distressed I encourage you to reach out to Brown CAPS. You may also find these resources from Brown Health and Wellness (and links therein) useful.