TAU CS 0368-424: Combinatorial Methods in Algorithms

Dr. Or Zamir       Spring 2025

In this class we will survey topics from discrete mathematics and graph theory, and their applications to the design of algorithms (and adjacent fields in theoretical computer science). Moreover, we will discuss algorithms solving problems from the world of combinatorics and graph theory. Among the topics we will cover are extremal graph theory, sampling and sparsifications of graphs, the graph regularity lemma, expander graphs, and others. We will apply these tools to solve algorithmic problems in various settings, including graph algorithms, sublinear time algorithms, conditional lower bounds, and more.

Lectures

• Lecture 1 (March 17): Finding triangles and 4-cycles in graphs, introduction to extremal graph theory, Mantel's theorem, Turan's theorem, Erdos-Stone-Simonovitz, extremal numbers of paths and even cycles, Bondy-Simonovitz, Moore's bound, graph spanners. [Scribe] [Homework]
• Lecture 2 (March 24): Randomized subgraph detection algorithms, finding 4-cycles in a sparse graph, Color Coding and finding fixed-sized paths and cycles of any size, extremal number and periodicity of theta-graphs. [Scribe 1] [Scribe 2] [Homework]
• Lecture 3 (March 31): Quicker detection of even cycles, proof of Bondy-Simonovitz, Fine-grained complexity: popular conjectures (SETH, APSP, Triangle), basic reductions (orthogonal vectors, graph diameter). [Scribe] [Homework]
• Lecture 4 (April 7): Conditional lower bounds for cycle detection, short cycle removal and conditional lower bounds for apporximation problems. [Scribe] [Homework]
• Lecture 5 (April 21): Sublinear time algorithms, property testing of bipartiteness (chromatic number), Szemeredi's regularity lemma, property testing of triangle-freeness (H-freeness). [Scribe] [Homework]
• Lecture 6 (April 28): Edge contractions in graph algorithms, Minimum Spanning Tree algorithms, Fredman-Tarjan, Minimum Cut algorithms, Karger and Karger-Stein, graph minors. [Scribe] [Homework]
• Lecture 7 (May 12): The Inclusion-Exclusion priniciple in algorithms. Algorithms for Hamiltonian paths and Set Partitioning Problems, including Graph Coloring. [Scribe] [Homework]