Open Problems:55 - Revision history

Krzysztof Onak: updated header

2013-03-07T01:59:58Z

updated header

Krzysztof Onak at 04:50, 12 December 2012

2012-12-12T04:50:54Z

Andoni at 01:48, 12 December 2012

2012-12-12T01:48:40Z

Andoni: Created page with "{{Header |title=Applications of Clifford Algebras in Graph Streams |source=dortmund12 |who=He Sun }} Some of the recent results in graph streaming algorithms {{cite|KaneMSS-12..."

2012-12-12T01:40:36Z

Created page with "{{Header |title=Applications of Clifford Algebras in Graph Streams |source=dortmund12 |who=He Sun }} Some of the recent results in graph streaming algorithms {{cite|KaneMSS-12..."

New page

{{Header
|title=Applications of Clifford Algebras in Graph Streams
|source=dortmund12
|who=He Sun
}}
Some of the recent results in graph streaming algorithms {{cite|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. {{cite|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. {{cite|ChienRS-03}} and discussed by Muthukrishnan {{cite|Muthukrishnan-05}}, by choosing elements of $D$ from $\mathbf{Z}$, $\mathbf{C}$, or a Clifford algebra $\mathbf{CL}$, 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.

@@ Line 6: / Line 6: @@
 Some of the recent results in graph streaming algorithms {{cite|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. {{cite|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. {{cite|ChienRS-03}} and discussed by Muthukrishnan {{cite|Muthukrishnan-06}}, by choosing elements of $D$ from $\mathbf{Z}$, $\mathbf{C}$, or a Clifford algebra $\mathbf{CL}$, 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.
+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. {{cite|ChienRS-03}} and discussed by Muthukrishnan {{cite|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 &ldquo;complex&rdquo; 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.
+'''Question:''' Find suitable applications of Clifford algebra in designing algorithms in graph streams.

@@ Line 1: / Line 1: @@
 {{Header
 |source=dortmund12
 |who=He Sun