ITCSC-INC Winter School 2012: Keywords

Network Coding
- Randomized coefficient matrix G: (i, j) : e[j] = G[i][j] * e[i]
- High Probability Det != 0
- Theorem: Cut(s, t) = Maximum information sent from s to t = #Linearly Independent vectors

Directed Graph connectivity
- F = H + GF, F = H * inv(I - G)
- High Probability: Min Cut = Matrix Rank
- Compute inv(I - G), Matrix for Cut(s, t) = extract submatrix from it

Single Source
- Topological sort, O(Δd²)
- Use Superconcentrators → O(Δd)

Expanders
- Sparse and highly connected
- Example: Bipartite Graph (n, 0.75n), left regular with constant number of edges
- High Probability: if |S| ≤ n/2 → |N(S)| ≥ |S|

Superconcentrators
- G(I, O): I, O = disjoint vertex sets
- For every k, choose k vertex from I, O and there exists k edge-disjoint path
- Construct: edge from I_i to O_i
- |I'| = 0.75|I|, |O'| = 0.75|O|, Expanders: (I, I'), (O', O)
- Recursively Superconcentrators G(I', O')

Matrix Rank
- Find linearly independent columns vectors for A_{m × n}
- Regular Bipartite Graph (n, 10m): left degree = 2, right degree = n/5m
- B[i] = Random Linear Combination of n/5m column vectors from A
- Done in O(#Non-zero entries in A)
- High Probability: Rank(B_{m × 10m}) = Rank(A_{m × n})
- Trace: at most n/5 vectors in A are candidate: reduce problem to A'_{m × n/5}