Spring 2026, Brown University
Doing research in theory and algorithms requires mathematical tools 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. Planned topics are: common asymptotic, inequality and proof strategies, randomization, polyhedral methods, metric embeddings and graph sparsification.
Enrollment in this course requires at least one of:
If your only prior exposure to the analysis of algorithms is CSCI500, you will likely need to play some catchup.
Additionally, you should have a solid background in
Above all else, you should be “mathematically mature” and have a strong background with formal proofs.
If you’re unsure if you have an appropriate background feel free to reach out and we can discuss!
In order to help you check for yourself if you have the required background and to refresh your understanding of these topics, I have put together some short review guides on each of the above 3 topics.
The first homework will be a review of these topics.
The class is broken into 5 sections as below.
| Date | Topic | Ellis’ Notes | Scribe Notes | Additional Resources |
| Basic Tools | ||||
| Jan 21 (Weds) | Class Overview, Learning, Doing and Writing Theory, Asymptotics | Slides on Class Overview, Slides on Learning, Doing and Writing Theory, Ellis’ Asymptotics Notes | TBD’s Scribe notes | See below links in “Other Resources” and Asymptopia by Spencer and Florescu or Asymptotic Methods in Analysis by N.G. de Brujin |
| Jan 28 (Weds) | Common Inequalities and Proof Strategies | Ellis’ Notes | TBD’s Scribe Notes | Cauchy-Schwarz Master Class by J. Michael Steele |
| Randomization | ||||
| Feb 4 (Weds) | Concentration, Common Randomized Paradigms, Hypercube Routing | Ellis’ Notes | TBD’s Scribe Notes | Probability and Computing by Mitzenmacher and Upfal, Concentration of Measure for the Analysis of Randomized Algorithms by Panconesi and Dubhashi |
| Feb 11 (Weds) | The Probabilistic Method, Union Bounds and the LLL | Ellis’ Notes | TBD’s Scribe Notes | The Probabilistic Method by Spencer and Alon |
| Polyhedral Methods | ||||
| Feb 18 (Weds) | LPs: the Algebraic and Linear Algebraic Views | Ellis’ Notes | TBD’s Scribe Notes | Understanding and Using Linear Programming by Matoušek and Gärtner or Theory of Linear and Integer Programming by Alexander Schrijver or Geometric Algorithms and Combinatorial Optimization by Grötschel, Lovász and Schrijver (if you want to go deep) or Linear Algebra Done Right by Axler |
| Feb 25 (Weds) | Exam 1: Basic Tools, Randomization (in class) | |||
| Mar 4 (Weds) | LPs: the Geometric View, LP Integrality | Ellis’ Notes | TBD’s Scribe Notes | A Course in Convexity by Barvinok |
| Mar 11 (Weds) | Duality, Hyperplane Separation and the Ellipsoid Algorithm | Ellis’ Notes | TBD’s Scribe Notes | |
| Metrics | ||||
| Mar 18 (Weds) | Randomized Rounding, Metrics, LDDs | Ellis’ Notes | TBD’s Scribe Notes | Approximation Algorithms by Williamson and Shmoys |
| Mar 25 (Weds) | No Class—Spring Break | |||
| Apr 1 (Weds) | Metric Embeddings, Random Projections, JL, Bourgain’s Embedding | Ellis’ Notes | TBD’s Scribe Notes | Lecture Notes on Metric Embeddings by Matoušek |
| Apr 8 (Weds) | l_1, the Cut Metric Cone, Sparsest Cut, Explanders | Ellis’ Notes | TBD’s Scribe Notes | Expanders Survey by Hoor, Linial and Widgerson |
| Graph Sparsification | ||||
| Apr 15 (Weds) | Distance and Routing Sparsification: Tree Embeddings | Ellis’ Notes | TBD’s Scribe Notes | |
| Apr 22 (Weds) | Exam 2: Polyhedral Methods, Metrics (in class) | |||
| TBD | Final Exam: Redo Topics |
Homeworks will be posted on Gradescope. You can ask questions about the homeworks on the Ed Discussion Board.
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.). I may also curve (upwards) depending on averages. If you’re just below a grade but consistently attend and participate in class, I may also round your grade up.
There will be 2 in-class exams and 1 final exam. Each of the 2 in-class exams will each test 2 topics from the class. The final will cover all 4 of basic tools, randomization, polyhedral methods and metrics.
Each of the exams will be a (random) subset of problems from the homeworks—possibly slightly modified—and will take place in class. You should bring something to write with (ideally a pencil and not a pencil). Exams are entirely closed-book.
Your exam grade will be calculated as follows. For each topic among basic tools, randomization, polyhedral methods and metrics you will receive a grade. Your exam grade is the average grade you get across these 4 topics. Your grade on each topic is the maximum between what you get on that topic on the in-class exam and on the final exam.
There will be 5 homeworks.
Homeworks are graded on completion. If you turn anything in before the deadline you will receive full credit. We will still provide feedback on your homework as if it were an exam.
There are no late days—again, note that homeworks are graded on completion and so you will get full credit as long as you turn something in before the deadline. Any homework turned in after the deadline will receive a 0.
Homeworks must be typeset in LaTeX. You may discuss problems together in groups but you must type-up and submit your own original homework. You may use computational mathematics tools to assist you (e.g. WolframAlpha, Maple, etc.). You may use ChatGPT or other LLM tools as you see fit.
Homeworks should be turned in via Gradescope.
For each class, one student will be responsible for writing “scribe notes” for the class. These are detailed notes summarizing what was described in class which are written in laTex and which must use [this scribe notes] template.
You can see example scribe notes from another course here.
For this course you are required to attend 2 talks of the Brown Theory Seminar. For each talk you must submit a ~150 word blurb of what research was described and how it relates to anything in which you are interested. These blurbs must be submitted on Gradescope. Anything reasonable will receive full credit.
Here some similar classes taught at other univertsities.
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.