Algorithms for Big Data (COMPSCI 229r), Lecture 11

Algorithms for Big Data (COMPSCI 229r), Lecture 11 Khintchine, decoupling, Hanson-Wright, proof of distributional JL lemma.

Algorithms for Big Data (COMPSCI 229r), Lecture 10

Algorithms for Big Data (COMPSCI 229r), Lecture 10 Harvard University explores streaming algorithm space lower bounds using communication complexity. The discussion transitions from proving these bounds for problems like distinct elements and disjointness to introducing dimensionality reduction as a method for managing high-dimensional data in large-scale geometric optimization tasks.

Algorithms for Big Data (COMPSCI 229r), Lecture 9

Algorithms for Big Data (COMPSCI 229r), Lecture 9 This lecture explores sophisticated techniques for establishing space lower bounds for streaming algorithms using communication complexity. The discussion covers foundational concepts like one-way protocols, the index problem, and information theory tools required to analyze the space complexity of algorithms for tasks such as calculating distinct elements and median estimation.

Algorithms for Big Data (COMPSCI 229r), Lecture 8

Algorithms for Big Data (COMPSCI 229r), Lecture 8 This lecture explores dynamic programming in the streaming model, specifically focusing on computing the longest increasing subsequence and distance to monotonicity. The discussion covers space-efficient randomized algorithms, compares their complexity to deterministic approaches, and addresses theoretical challenges in maintaining DP tables with sublinear space requirements.

Algorithms for Big Data (COMPSCI 229r), Lecture 7

Algorithms for Big Data (COMPSCI 229r), Lecture 7 This lecture explores L0 sampling as a foundational primitive for processing streaming graph data. Participants examine algorithms for maintaining sketches under turnstile model updates, effectively addressing connectivity and related graph problems using significantly less space than traditional edge-storing methods.