CS 860 (01): Modern Topics in Graph Algorithms (Winter 2024)

Did NOT work :|

Lectures Mondays 3:00 PM to 5:50 PM in DC 2585
Instructor Sepehr Assadi        (userid: sassadi)
Instructor office hours Mondays 10:00 AM (by appointment)
Prerequisites Mathematical maturity, and a strong background in undergraduate-level probability theory, data structures, and algorithm design are all essential.
Textbook There is no official textbook. Lecture notes and other required materials will be posted on this webpage.
Course outline The course outline will be posted here at some point before the start of the term. This page contains the highlights of course outline that can be updated as the term progresses.
Communication The lectures will be delivered on the blackboard. We use LEARN for assignments and grades. For specific concerns, questions, or comments regarding your experience in the course, you can directly email me @ (sassadi).

Topics

Last decade or so have witnessed major advances in the study of graph algorithms, including solutions to longstanding problems, development of various new tools and techniques, and introduction of new models and frontiers in research on graphs. This course covers some of the highlights in this area, ranging from fast graph algorithms in classical setting using advanced techniques such as sparsification, convex optimization, graph decompositions, etc., to various modern models of graph algorithms including streaming, sublinear-time, dynamic, and distributed algorithms.

The course has no formal prerequisite but mathematical maturity, and a strong background in undergraduate-level probability theory, data structures, and algorithm design are all essential. The courseload involves participating in lectures, scribing notes, and solving algorithmic problems.

The following is a tentative list of the topics that we will cover in this course (not necessarily in this particular order):

• Graph Sparsification: Cut/spectral sparsifiers, Spanners, Palette sparsification, Edge-degree constrained subgraphs
• Hopsets, Shortcuts, Spanners: Graph shortcutting, Additive spanners, Emulators and distance preservers
• Extremal Graph Theory: Ruzsa-Szemeredi (RS) Graphs, Shortcutting Graphs, Matching sparsifiers, Additive spanners
• Minimum Cuts: Tree packing, Isolating cut, Vertex connectivity
• Maximum Matchings: Edmond's algorithm, Primal-dual approximation algorithms, Recent advances
• Shortest paths: Low diameter decompositions, Tree embeddings, Negative-weight shortest path
• Maximum Flow: Multiplicative weight method, Congestion approximators, Oblivious routing, Recent advances
• Graph coloring: Approximation algorithms, Edge coloring and Vizing's theorem, Fast (Delta+1) vertex coloring
• Streaming algorithms: Maximum matchings, Transhipment
• Sublinear time algorithms: Connected components, Approximate matching/vertex cover
• Distributed (LOCAL) algorithms: Maximal Independent Set (MIS) algorithms, Network decompositions
• Dynamic graph algorithms: Connectivity, Approximate matching
• Parallel algorithms: Matching in RNC, Isolation lemma, Derandomization, Massively Parallel Computation (MPC) algorithms

Grading

The final grade for the course will be based on the following weights:

The course outline contains more details on the grading scheme of this course and collaboration policies and groups for the problem sets and scribe notes.

Course Calendar

The schedule below the red line is tentative and subject to change (including potentially the release and due dates for problemsets).

# Date Topics Lecture notes & References Problemsets
1 Monday
Jan 15
Minimum Spanning Trees: A Linear-Time Randomized Algorithm [lec1], KKT95, K97, BF00
2 Monday
Jan 22
Maximum Matchings: Primal-Dual Algorithms [lec2], E65, B88
3 Monday
Jan 29
(Δ+1) Vertex Coloring: Palette Sparsification [lec3], ACK19, MR97, R98
4 Monday
Feb 05
Graph Shortcutting: Extremal Results and Algorithms KP22, H03
5 Monday
Feb 12
Triangle Detection and Matrix Multiplication HW1 release: [HW1]
Monday
Feb 19
No class: Reading Week

6 Monday
Feb 26
Expander Decomposition: A Simple Application to Minimum Cuts
7 Monday
March 04
Algorithms for Expander Decomposition HW1 due
8 Monday
March 11
Isolating Cuts for Minimum Cut Problems
9 Monday
March 18
Multiplicative Weight Update Method
10 Monday
March 25
Laplacian Paradigm: Faster Approximate Maximum Flow
11 Monday
April 01
Negative Weight Shortest Path in Near-Linear Time
* Monday
April 08
End of classes

Resources

There is no official textbook for the course (most of our material is not in textbooks yet anyway). The following resources are all optional but they can be quite helpful and I encourage you to refer to them throughout the term for more details on the topics we cover in the class.

Workshop on Modern Techniques in Graph Algorithms

Possibly the best resource to familiarize yourself with the topics of this course is the Workshop on Modern Techniques in Graph Algorithms that was held at DIMACS in Summer 2023, organized by Prantar Ghosh, Zihan Tan, and Nicole Wein.

Further Reading

For some related textbooks and surveys, you can refer to:

MR13 Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms. Cambridge University Press, 2013.
DP09 Devdatt P. Dubhashi and Alessandro Panconesi, Concentration of Measure for the Analysis of Randomised Algorithms. Cambridge University Press, 2009.
AS16 Noga Alon and Joel H. Spencer, The Probabilistic Method, 4th Edition. Wiley, 2016.
V20 Nisheeth K. Vishnoi, Algorithms for Convex Optimization. © Copyright 2020 Nisheeth K. Vishnoi.
AHK12 Sanjeev Arora, Elad Hazan, Sagar Kale, The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing, 2012.

Bibliography

This is a (rather incomprehensive) list of the papers related to the topics discussed in the lectures. The list will be updated frequently throughout the term.

ACK19 Sepehr Assadi, Yu Chen, Sanjeev Khanna Sublinear Algorithms for (Δ+1) Vertex Coloring. SODA 2019.
B88 Dimitri P Bertsekas, The auction algorithm: A distributed relaxation method for the assignment problem. Annals of operations research 1988.
BF00 Michael A. Bender and Martin Farach-Colton, The LCA Problem Revisited. LATIN 2000.
E65 Jack Edmonds, Paths, trees, and flowers. Canadian Journal of mathematics 1965.
H03 William Hesse, Directed graphs requiring large numbers of shortcuts. SODA 2003.
K97 Valerie King, A simpler minimum spanning tree verification algorithm. Algorithmica 1997.
KKT95 David R. Karger, Philip N. Klein, Robert Endre Tarjan, A randomized linear-time algorithm to find minimum spanning trees. JACM 1995.
KP22 Shimon Kogan, Merav Parter, New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the sqrt{n} Barrier. SODA 2022.
MR97 Michael Molloy, Bruce Reed, A bound on the strong chromatic index of a graph. Journal of Combinatorial Theory 1997.
R98 Bruce Reed, ω, δ, and χ. Journal of Graph Theory 1998.

Resources on LaTeX

You can download LaTeX for free. For the purpose of this course, you do not even need to install LaTeX and can instead use an online LaTeX editor such as Overleaf.

Two great introductory resources for LaTeX are Getting started with TeX, LaTeX, and friends by Allin Cottrell (for general purpose LaTeX) and LaTeX for Undergraduates by Jim Hefferson (for undergraduates mathematics) accompanied by the following cheatsheet (note that this document use "\( MATH \)" notation compared to the perhaps more widely used "$ MATH $" -- both are completely fine in LaTeX). You can also use this wonderful tool Detexify by Daniel Kirsch for finding the LaTeX commands of a symbol (just draw the symbol!).

If you are interested in learning more about LaTeX (beyond what is needed for this course), check the Wikibook on LaTeX and the Wikibook on LaTeX for Mathematics.

Policies and Statements

Territorial Acknowledgement

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.

Students with Disabilities

You are encouraged to discuss with me any appropriate accommodations that we might make on your behalf following the guidelines of the AccessAbility Services.

AccessAbility Services, located in Needles Hall, Room 1401, collaborates with all academic departments/schools to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with AccessAbility Services at the beginning of each academic term.

Statement of Inclusivity

I am committed to creating a learning environment in which all of my students feel safe and included, regardless of race, ethnicity, religion, gender or sexual orientation. Because we are individuals with varying needs, I rely on your feedback to achieve this goal. I invite you to let me know about what I can stop, start, or continue doing to make sure every one of my students feels valued and can engage actively in our learning community.

Faculty of Math Statement on Diversity: It is our intent that students from all diverse backgrounds and perspectives be well served by this course, and that students’ learning needs be addressed both in and out of class. We recognize the immense value of the diversity in identities, perspectives, and contributions that students bring, and the benefit it has on our educational environment. Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally or for other students or student groups. In particular:

Your Health & Well-Being

This is a challenging course with various advanced topics and not-so-easy assignments and exams. All of these are going to be time and energy consuming. But, this is also an elective course so one of my main goals is for you to enjoy taking this course and learning these cool materials as much as I enjoy teaching them. Part of making sure you have fun involves taking care of yourself. Do your best to maintain a healthy lifestyle and work-life balance this term by eating well, exercising, getting enough sleep, and taking some time to relax -- all of these will tremendously help you to achieve your goals in the course and to enjoy the process in the meantime.

You can find more resources to help you with your health & well-being with the Campus Wellness and Student Success Office -- they have tons of resources on helping you to succeed, including very good tips on time management techniques.

Faculty of Math Statement on Mental Health: The Faculty of Math encourages students to seek out mental health support if needed:

On-campus Resources: Off-campus Resources:

Rights and Responsibilities

Every member of this class---instructor, TA, and students---has rights and responsibilities toward having a pleasant, fair, supportive, and free of discrimination and micro-aggression environment in this course, and we are all answerable to the University policies governing ethical behaviour (Policy 33).

In addition, academic dishonesty and plagiarism is considered a serious offense in this course. I expect that any assignment or exam you submit in this course will be your own product and follows the collaboration and external resources policies specified in the course outline. If an assignment is too hard, start earlier, ask for help, or simply do not answer the question --- academic dishonesty is never the right answer. If you have any concerns or questions about these policies, please discuss them with me.

Finally, a reminder that all the course content including lecture notes, presentations, and other materials prepared for the course, are the intellectual property (IP) of the instructor. These course materials are available to you to enhance your educational experience, and sharing them without permission and proper citation is a violation of intellectual property rights.

University Policies: It is your job to know the university policies that govern your behaviour in this course. Some pointers are: Intellectual Property: Students should be aware that this course contains the intellectual property of their instructor, TA, and/or the University of Waterloo. Intellectual property includes items such as:

Course materials and the intellectual property contained therein, are used to enhance a student’s educational experience. However, sharing this intellectual property without the intellectual property owner’s permission is a violation of intellectual property rights. For this reason, it is necessary to ask the instructor, TA and/or the University of Waterloo for permission before uploading and sharing the intellectual property of others online (e.g., to an online repository).

Permission from an instructor, TA or the University is also necessary before sharing the intellectual property of others from completed courses with students taking the same/similar courses in subsequent terms/years. In many cases, instructors might be happy to allow distribution of certain materials. However, doing so without expressed permission is considered a violation of intellectual property rights.

Please alert the instructor if you become aware of intellectual property belonging to others (past or present) circulating, either through the student body or online. The intellectual property rights owner deserves to know (and may have already given their consent).

Use of Generative Artificial Intelligence: The following statement is prepared by the Office of Academic Integrity with input from the Centre for Teaching Excellence, Library, and consultations with Associate Deans and members of the Standing Committee on New Technologies, Pedagogy, and Academic Integrity (Last Updated: August 2023):

Generative artificial intelligence (GenAI) trained using large language models (LLM) or other methods to produce text, images, music, or code, like Chat GPT, DALL-E, or GitHub CoPilot, may be used for assignments in this class with proper documentation, citation, and acknowledgement. Recommendations for how to cite GenAI in student work at the University of Waterloo may be found through the Library.

Please be aware that generative AI is known to falsify references to other work and may fabricate facts and inaccurately express ideas. GenAI generates content based on the input of other human authors and may therefore contain inaccuracies or reflect biases. In addition, you should be aware that the legal/copyright status of generative AI inputs and outputs is unclear. Exercise caution when using large portions of content from AI sources, especially images. More information is available from the Copyright Advisory Committee.

You are accountable for the content and accuracy of all work you submit in this class, including any supported by generative AI.


Created & maintained by Sepehr Assadi