Fall 2024, Brown University
Time and Location
Tuesday, Thursday, 9:00AM – 10:20AM, CIT 477 (Lubrano)
Instructor
Ellis Hershkowitz, CIT 507
Office Hours
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.
| Date | Topic | Class Notes | Additional Resources |
| Basic Tools | |||
| Sep 5 (Thurs) | Overview of Class + Learning, Doing and Writing Theory | Slides on Class Overview and Slides on Learning, Doing and Writing Theory | See below links in “Other Resources “ |
| Sep 10 (Tues) | Asymptotics | Ellis’ notes | Asymptopia by Spencer and Florescu or Asymptotic Methods in Analysis by N.G. de Brujin |
| Sep 12 (Thurs) | Common Inequalities | Ellis’ notes | Cauchy-Schwarz Master Class by J. Michael Steele |
| Sep 17 (Tues) | Common Proof Strategies | Ellis’ notes | |
| Randomization | |||
| Sep 19 (Thurs) | Probability Review and Gaussians | Ellis’ notes | Probability and Computing by Mitzenmacher and Upfal |
| Sep 24 (Tues) | Concentration and Common Randomized Paradigms | Ellis’ notes | Concentration of Measure for the Analysis of Randomized Algorithms by Panconesi and Dubhashi |
| Sep 26 (Thurs) | Using Randomization: Hypercube Routing | Ellis’ notes | |
| Oct 1 (Tues) | The Probabilistic Method, Union Bounds and the LLL | Ellis’ notes | The Probabilistic Method by Spencer and Alon |
| Polyhedral Methods | |||
| Oct 3, Oct 8 (Thurs+Tues) | Linear Programs: the Algebraic View | Ellis’ 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) |
| Oct 10 (Thurs) | Linear Programs: the Linear Algebraic View | Ellis’ notes | Ellis’ Linear Algebra Review or Linear Algebra Done Right by Axler |
| Oct 15 (Tues) | Linear Programs: the Geometric View | Ellis’ notes | A Course in Convexity by Barvinok |
| Oct 17 (Thurs) | Using LPs: LP Integrality | Ellis’ notes | |
| Oct 22 (Tues) | Duality + Hyperplane Separation Theorems | Ellis’ notes | |
| Oct 24 (Thurs) | The Ellipsoid Algorithm | Ellis’ notes | |
| Oct 29 (Tues) | Using LPs: Randomized Rounding + Primal-Dual | Ellis’ notes | Approximation Algorithms by Williamson and Shmoys |
| Geometry and Metric Embeddings | |||
| Oct 31 (Thurs) | LPs Meet Metrics: LDDs and Rounding the Multicut LP | Ellis’ notes | |
| Nov 5 (Tues) | No Class, Election Day | ||
| Nov 7 (Thurs) | Metric Embeddings, Random Projections and Johnson-Lindenstrauss | Ellis’ notes | Lecture Notes on Metric Embeddings by Matoušek |
| Nov 12 (Tues) | l_p Metrics, Bourgain’s Embedding and The Cut Metric Cone | ||
| Cuts and Flows | |||
| Nov 19 (Tues) | Multi-Commodity Flow-Cut Gap and Sparsest Cut | ||
| Nov 21 (Thurs) | Expanders and Expander Decompositions | Expanders Survey by Hoor, Linial and Widgerson | |
| Graph Sparsification | |||
| Nov 21 (Thurs) | Cut Sparsification: Gomory-Hu Trees (+ Uncrossing) | ||
| Nov 26 (Tues) | Distance Sparsification: Probabilistic Tree Embeddings | ||
| Nov 28 (Thurs) | No Class, Thanksgiving Break | ||
| Dec 3 (Tues) | Flow Sparsification: Oblivious Routing via Raecke Trees | ||
| Multiplicative Weights | |||
| Dec 5 (Thurs) | The Experts Framing | MW Survey by Arora, Hazan and Kale | |
| Dec 10 (Tues) | Fast Multi-Commodity Flow | ||
| Dec 12 (Thurs) | Online Set Cover |
The homeworks will be posted on Gradescope. You can ask questions about the homeworks on the Ed Discussion Board.
The exam will be posted on Gradescope.
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.
Homeworks must be typeset in LaTeX. You may discuss problems together in groups of up to four 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 not search for answers to homework problems online. You may not use ChatGPT or other LLM tools. Each of your homeworks must state with whom, if anybody, you discussed problems. Homeworks should be turned in via Gradescope. Any homework that does not abide by the above will receive a 0.
You have five (5) late days to use on homeworks as you see fit. If you have no remaining late days and your homework is turned in late, you will receive a 0 for it.
Here are some additional resources that you may find useful.
Similar Classes
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.