Open Problems:55

Suggested by	He Sun
Source	Dortmund 2012
Short link	https://sublinear.info/55

Some of the recent results in graph streaming algorithms [KaneMSS-12,ManjunathMPS-11] use complex-valued sketches to capture the graph structure. While it had been known earlier that integer-valued sketches can be used to count triangles, Kane et al. [KaneMSS-12] developed a complex-valued sketch to count the number of occurrences of an arbitrary subgraph of constant size. These techniques also extend to variations of the subgraph counting problem, for instance counting a directed or (labelled) subgraph. However, the bounds on the space complexity which depends on the variance of the sketches are quite loose for most graph families.

It is interesting to compare these results to the framework of designing randomized algorithms for computing the permanent. Let $A$ be a 0-1 matrix, and $B$ be the matrix obtained from $A$ by replacing each 1 uniformly and randomly with an element from a finite set $D$. With suitable choices of the set $D$, the determinant of $B$ can be used to approximate the permanent of $A$. As shown by Chien et al. [ChienRS-03] and discussed by Muthukrishnan [Muthukrishnan-06], by choosing elements of $D$ from $\mathbb Z$, $\mathbb C$, or a Clifford algebra, the variance of the estimator drops significantly each time when we move to a more “complex” algebra. It seems plausible that similar techniques can be used to improve the space complexity of graph streaming algorithms which are based on complex-valued random variables.

Question: Find suitable applications of Clifford algebra in designing algorithms in graph streams.