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
To help you check for yourself if you have the required background and to refresh your understanding of these topics, the first homework (released on the first day of class) will consist of review guides on probability and linear algebra with in-line problems.
Additionally, you should be comfortable with the basics of the theory of NP-completeness and calculus.
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!
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 | Class Overview, Learning, Doing and Writing Theory, Asymptotics | Maryam | 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 | Inequalities, Proof Strategies | Additi, Alp | Cauchy-Schwarz Master Class by J. Michael Steele |
| Randomization | ||||
| Feb 4 (Weds) | Concentration, Hypercube Routing | Concentration, Routing | Ping, Na | 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 | Probabilistic Method, LLL Algorithms | Renxuan, Joshua | The Probabilistic Method by Spencer and Alon, Terry Tao Entropy Compression Blog Post |
| Polyhedral Methods | ||||
| Feb 18 (Weds) | LPs: the Algebraic and Linear Algebraic Views | Ellis’ Notes | Qianyun, Alice | 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 | Sunny, Ryan | A Course in Convexity by Barvinok |
| Mar 11 (Weds) | Duality, Hyperplane Separation and the Ellipsoid Algorithm | Ellis’ Notes | George, Louis | |
| Metrics | ||||
| Mar 18 (Weds) | Randomized Rounding, Metrics, LDDs | Ellis’ Notes | Jack, Sri | 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 | Gabe, Jake | Lecture Notes on Metric Embeddings by Matoušek |
| Apr 8 (Weds) | l_1, the Cut Metric Cone, Sparsest Cut, Expanders | Ellis’ Notes | Will, Klara | Expanders Survey by Hoor, Linial and Widgerson |
| Graph Sparsification | ||||
| Apr 15 (Weds) | Distance and Routing Sparsification: Tree Embeddings | Ellis’ Notes | Aamen, Phuoc | |
| 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.
For all portions of the course except for the exams, you may use computational mathematics tools to assist you (e.g. WolframAlpha, Maple, etc.) and ChatGPT or other LLM tools as you see fit.
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.
Due dates are listed above. Generally, each homework is out for the duration of the topic that it covers.
Homeworks should be turned in via Gradescope.
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 pen). 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.
See the above schedule for the dates.
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.
These are due 4/29/2026.
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.
Reasonable scribe notes will receive full credit. Anything incomplete may not.
The notes for a given class are due (on Gradescope) within 2 weeks from the day of the class for which they are scribe notes. You must write your scribe notes in the course Overleaf and then additionally turn in a pdf on Gradescope. A link to the course Overleaf is available in the assignment on Gradescope.
You can see example scribe notes from another course here.
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.