Lecture Notes for CS 6550: Advanced Graduate Algorithms (Randomized and Approximation Algorithms)

Introduction
Karger's min-cut algorithm
The algorithm
Analysis
The Karger-Stein algorithm
The algorithm
Analysis
Classical Median Finding Algorithms
Find Median With High Probability
Analysis
Runtime Analysis
Failure Probability
Bernoulli Random Variables and Chebychev's Inequality
Proofs
Chernoff Bounds
Markov and Chebyshev Inequality
Chernoff ``argument" for Bin(n,12)
Chernoff Inequality
Warm-up example: Median estimate
Problem definition
Solution
Analysis
Streaming
Problem definition
Solution
Analysis
Example: Frequency Moments
F2 Estimation
Distinct Elements
Pairwise Independent
Simple Construction
Hashing
Application: Streaming
The AMS algorithm
Analysis of Algorithm
Space Complexity
Failure Probability
Maximal Independent Sets
Expected Running Time
Derandomizing MIS
History and Open Questions
Data Streaming
The algorithm
Preliminaries: The Data Stream Model
The Basic Setup
The Quality of an Algorithm's Answer
Variations of the Basic Setup
Finding Frequent Items Deterministically
The Problem
Frequency Estimation: The Misra–Gries Algorithm
Analysis of the Algorithm
Finding the Frequent Items
Exercises
Estimating the Number of Distinct Elements
The Problem
The Tidemark Algorithm
The Quality of the Algorithm's Estimate
The Median Trick
Exercises
A Better Estimate for Distinct Elements
The Problem
The BJKST Algorithm
Analysis: Space Complexity
Analysis: The Quality of the Estimate
Optimality
Exercises
Approximate Counting
The Problem
The Algorithm
The Quality of the Estimate
The Median-of-Means Improvement
Exercises
Finding Frequent Items via (Linear) Sketching
The Problem
Sketches and Linear Sketches
CountSketch
The Quality of the Basic Sketch's Estimate
The Final Sketch
The Count-Min Sketch
The Quality of the Algorithm's Estimate
Comparison of Frequency Estimation Methods
Exercises
Estimating Frequency Moments
Background and Motivation
The (Basic) AMS Estimator for Fk
Analysis of the Basic Estimator
The Final Estimator and Space Bound
The Soft-O Notation
The Tug-of-War Sketch
The Basic Sketch
The Quality of the Estimate
The Final Sketch
A Geometric Interpretation
Exercises
Estimating Norms Using Stable Distributions
A Different 2 Algorithm
Stable Distributions
The Median of a Distribution and its Estimation
The Accuracy of the Estimate
Annoying Technical Details
Sparse Recovery
The Problem
Special case: 1-sparse recovery
Analysis: Correctness, Space, and Time
General Case: s-sparse Recovery
Exercises
Weight-Based Sampling
The Problem
The 0-Sampling Problem
An Idealized Algorithm
The Quality of the Output
2 Sampling
An 2-sampling Algorithm
Analysis:
Finding the Median
The Problem
Preliminaries for an Algorithm
The Munro–Paterson Algorithm
Computing a Core
Utilizing a Core
Analysis: Pass/Space Tradeoff
Exercises
Geometric Streams and Coresets
Extent Measures and Minimum Enclosing Ball
Coresets and Their Properties
A Coreset for MEB
Data Stream Algorithm for Coreset Construction
Exercises
Metric Streams and Clustering
Metric Spaces
The Cost of a Clustering: Summarization Costs
The Doubling Algorithm
Metric Costs and Threshold Algorithms
Guha's Cascading Algorithm
Space Bounds
The Quality of the Summary
Exercises
Graph Streams: Basic Algorithms
Streams that Describe Graphs
Semi-Streaming Space Bounds
The Connectedness Problem
The Bipartiteness Problem
Shortest Paths and Distance Estimation via Spanners
The Quality of the Estimate
Space Complexity: High-Girth Graphs and the Size of a Spanner
Exercises
Finding Maximum Matchings
Preliminaries
Maximum Cardinality Matching
Maximum Weight Matching
Exercises
Graph Sketching
The Value of Boundary Edges
Testing Connectivity Using Boundary Edges
Testing Bipartiteness
The AGM Sketch: Producing a Boundary Edge
Counting Triangles
A Sampling-Based Algorithm
A Sketch-Based Algorithm
Exercises
Communication Complexity and a First Look at Lower Bounds
Communication Games, Protocols, Complexity
Specific Two-Player Communication Games
Definitions
Results and Some Proofs: Deterministic Case
More Proofs: Randomized Case
Data Streaming Lower Bounds
Lower Bound for Majority
Lower Bound for Frequency Estimation
Exercises
Further Reductions and Lower Bounds
The Importance of Randomization
Multi-Pass Lower Bounds for Randomized Algorithms
Graph Problems
The Importance of Approximation
Space versus Approximation Quality
Exercises
Derandomization of an Algorithm
Maximal Independent Set Algorithm
Sequential Algorithm
Parallel Algorithm
Proof with Pairwise Independence
Maximal Independent Sets
Expected Running Time
Derandomizing MIS
History and Open Questions
Maximum Satisfiability (MAX-SAT)
Problem Statement
Random Assignment
Derandomization
Randomized Rounding
Integer (Linear) Programming
Reduction
Algorithm
A Third Algorithm
Max-Cut Problem
Simple 12-approximation Algorithm
Max-Cut as an Integer Linear Programming (ILP) Problem
Semi-definite Programming
Summary
Polynomial identity testing
Matrix multiplication
Polynomial Equality Testing
Perfect Matching
Preliminaries in number theory
RSA encryption algorithm
Correctness
Implementation
Primality testing
Fermat witness
Primality Test when n is not Carmichael
Correctness
Millerâ•fiRabin Primality Test
Correctness
Dimension Reduction
The Johnson Lindenstrauss lemma
The construction
Some properties of Gaussians
The proof
The proof, this time for real
The Expectation
Concentration about the Mean
Using Random Signs instead of Gaussians
Concentration Around the Mean via Subgaussian-ness
Compressive Sensing
The Curse of Dimensionality in the Nearest Neighbor Problem
Point of Lecture
Role Model: Fingerprints
L2 Distance and Random Projections
The High-Level Idea
Review: Gaussian Distributions
Step 1: Unbiased Estimator of Squared L2 Distance
Step 2: The Magic of Independent Trials
The Johnson-Lindenstrauss Transform
Jaccard Similarity and MinHash
The High-Level Idea
MinHash
A Glimpse of Locality Sensitive Hashing
Generic Primal-Dual Algorithm
2( 1 - 1k ) - approximation algorithm for steiner tree problem
Steiner Tree Problem
Primal
Dual
Algorithm
Analysis
Lovasz Local Lemma
Lemma1
Lemma2
Lovasz Local Lemma
Asymmetric Lovasz Local Lemma
Algorithmic Lovász Local Lemma
Witness trees
Proof of Algorithmic Lovász Local Lemma
Introduction
Execution logs and witness trees
Random generation of witness trees
Analyzing the parallel algorithm
A deterministic variant
The Lopsided Local Lemma
Conclusion
Introduction
Bloom Filters
Bloom Filter Algorithms for Operations
Bloom Filter Querying Analysis
Bloom Filter Time Complexities
Cuckoo Hashing
Cuckoo Filter Algorithms for Operations
Cuckoo Hashing Analysis
Conclusion
#DNF
Problem Statement
The Monte Carlo Method
Applying the Monte Carlo Method to #DNF
Choosing a Better Sample Space
The Network Unreliability Problem
Problem Statement
Overview
pC n-4
Enumerating small cuts
A FPRAS for #DNF
pC n-4
Putting it all together
Open problems
2-SAT
A randomized algorithm
Analysis
Markov Chain
Definitions
Properties
PageRank
Problem Statement
Sampling and Counting
Canonical Path
Example: Random walk on hypercube