| Date |
Speaker |
Paper Title |
Topics Covered |
| May 16, 2023 |
Siddhartha Sarkar |
Weighted Geometric Set Cover via Quasi-Uniform Sampling |
- Quasi-uniform sampling technique
- O(logloglog n)-approximate set cover for fat triangles
- Union complexity
|
| May 23, 2023 |
Mohit Garg |
Coloring and Maximum Weight Independent Set of Rectangles |
- O(w^2)-coloring for rectangles
- O(w)-coloring of rectangles with only special types of intersections
|
| May 30, 2023 |
- Hierarchical decomposition
- O(w)-coloring of rectangles with only special types of intersections
|
| June 06, 2023 |
Aditya Subramanian |
Almost Optimal Set Covers in Finite VC-Dimension |
- Shattering dimension
- O(dlog OPT)-approx for set cover with VC-dim = d
|
| June 12, 2023 |
Rachana Gusain |
Persistent data structures |
|
| June 20, 2023 |
Nikhilesh Rajaraman |
Online and Dynamic Algorithms for Set Cover |
- Stable set covers
- Greedy algorithm through an alternate lens
- Dynamically maintaining set/element levels
|
| June 28, 2023 |
- Analysis using charging argument
|
| July 04, 2023 |
- Primal-dual analysis through charging using budgets
|
| July 18, 2023 |
Debajyoti Kar |
Near-Linear Algorithms for Geometric Hitting Sets and Set Covers |
- Zero sum games
- Approximate Nash Equilibrium using MWU
- O(loglog OPT)-approximation for hitting set for rectangles
- BST, Segment tree
|
| July 25, 2023 |
Pranjal Singh (guest) |
Independence number of intersection graphs of axis-parallel segments |
- Favorable representation
- Erdos-Szekeres theorem
|
| August 02, 2023 |
Siddhartha Sarkar |
Approximation Algorithms for Maximum Independent Set of Pseudo-Disks |
- Local search analysis using union complexity
- Frederickson’s planar separator theorem
- PTAS for MIS on Pseudodisks
|
| August 08, 2023 |
- Resistance
- Clarkson’s technique
- u(n)/n-approximation for weighted geometric MIS
|
| August 17, 2023 |
Mohit Garg |
Computing the Independence Number of Intersection Graphs |
- Separators in string graphs
- Exact algorithms for MIS on string graphs
|
| August 24, 2023 |
Aditya Subramanian |
Hitting sets online and unique max-coloring |
- Vertex ranking
- Theta(log n)-approximation for online hitting sets on intervals
- Chen et al.’s Plane partitioning technique
|
| August 31, 2023 |
- Theta(log n)-approximation for online hitting sets on unit disks
|
| September 05, 2023 |
Rachana Gusain |
Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles |
- Hierarchical grid decomposition
- Data structure to report smallest hypercube inside a box
|
| September 12, 2023 |
- Dynamic DP over hierarchical grid
- Analysis of greedy algorithm via charging
- (1+eps).2^d-approximation in polylog update time for dynamic MIS on hypercubes
|
| October 03, 2023 |
Nikhilesh Rajaraman |
On Dynamic Graph Algorithms with Predictions |
- Dynamic All Pairs Shortest Paths (APSP) with predictions
|
| October 26, 2023 |
- Dynamically maintaining matrix inverse with column updates in O(n^2) time
- Woodbury matrix identity
- Dynamic s-t connectivity in O(n^2) update time
|
| October 12, 2023 |
Debajyoti Kar |
Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods |
- Inductive independence number
- 8.rho^2-approximation for unweighted MIS in Secretary model
|
| October 19, 2023 |
- O(rho^2 log n)-approximation for weighted MIS in Secretary model
- Omega(log n/(loglog n)^2) lower bound
|
| November 11, 2023 |
Aditya Subramanian |
Tight Bounds for Online Weighted Tree Augmentation |
- Caterpillar decomposition
- Rooted path decomposition of width O(log n)
|
| December 07, 2023 |
- Suboptimal O(log^2 n)-approximation for online WTAP
- Strategy to get O(log n)-approximation using “nice” feasible solution of WPAP
- LP relaxation for online WPAP
|
| December 12, 2023 |
- Omega(log n) lower bound for online WPAP
- Omega(log n) lower bound for online (unweighted) TAP
|
| January 25, 2024 |
- Overview of O(log n) online WPAP
- Proof of niceness via duality
|
| January 30, 2024 |
|
| February 09, 2024 |
Siddhartha Sarkar |
Packing and Covering with Non-Piercing Regions |
- Lens Bypassing to characterize non-piercing regions
- Locality preserving property
- Outline of algorithm using planar separators
|
| February 20, 2024 |
- Construction of locality preserving graph
|
