Week 10 (Streaming Algorithms)

Question 1

What is a streaming algorithm?

Answer 1

For a model with a known set of vertices V and edges that arrive one-by-one, we can decide to keep them or not.

Question 2

What is the upper bound with streaming algorithms?

Answer 2

Upper bound of O(n^2) bits to store the whole adjacency matrix or O(n^2 log n) if we want to remember each edge and endpoint

Question 3

What is the lower bound for many simple problems for streaming algorithms?

Answer 3

Ω(n^2) bits

Question 4

What is the index problem?

Answer 4

Alice has X = {X1,…,Xn} ∈ {0,1}^N and Bob has an index i ∈ [N] and wants to find Xi

Question 5

What is the one-way communication method for the index problem?

Answer 5

If we allow one way communication, Alice must send over all n bits giving an upper bound of n bits.

Question 6

What is the two-way communication method for the index problem?

Answer 6

With two way communication, Bob can tell Alice the index i using log(i) bits and Alice can return Xi for an overall complexity of log(n) + 1 bits

Question 7

What is the proof behind the lower bound of the index problem?

Answer 7

Alice needs to send at least N bits. Alice has a possible 2^N inputs.

Suppose Alice sends over <= (N-1) bits to Bob which gives <= 2^n-1 different information to Bob. Propose two pieces of information X and X’ which aren’t equivalent. After removing one index, Alice sends over the same information to Bob for both X and X’, so Bob gets the same value for Xi but X != X.

There is a lower bound of Ω(n^2) bits on 1-way communication from Alice to Bob even allowing randomisation, with probability > 1/2

Question 8

How can we see if a graph has a cycle using a streaming algorithm?

(Uses the index problem)

Answer 8

Let [r] = {1,…,r} and [N] = {1,…,N}
- Alice and Bob fix a bijection Φ: [r]x[r] -> [N]
- For each i ∈ [N], if Xi = 1 then Alice adds an edge between as and bt where (s,t) = Φ^-1 (i)
- Bob has index I ∈ [N] and computes Φ^-1 (I) = (s, t)
- Bob adds a new vertex z and adds two edges as* - z and bt* - z
- If G has a cycle, then Xi = 1

If Xi = 1, then there exists a cycle between a,b and z. If Xi = 0 then there is no edge between a and b and so no cycle.

Any streaming algorithm for checking if ∃ a cycle can solve the index problem, which has a lower bound of Ω(n^2) bits. Because G has (2r+1) vertices, checking if ∃ a cycle on n-vertex graphs has Ω(n^2) bits lower bound.

Question 9

What is the streaming algorithm for minimum vertex cover?

Answer 9

Let [r]={1,…,r} and [N] = {1,…,N}
- Alice and Bob fix a bijection Φ: [r]x[r] -> [N]
- For each i ∈ [N], if Xi = 1 then Alice adds an edge between as and bt where (s,t) = Φ^-1 (i)
- Bob has index I ∈ [N] and computes Φ^-1 (I) = (s, t)
- Bob adds two leaves for each vertex in A\as* and B\bt*
- If G is a MinVC of size 2(r-1)+1 then Xi = 1