Difference between revisions of "Open Problems:55"
(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...") |
m (updated header) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|source=dortmund12 | |source=dortmund12 | ||
|who=He Sun | |who=He Sun | ||
| Line 6: | Line 5: | ||
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. | 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- | + | 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 “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''' | + | '''Question:''' Find suitable applications of Clifford algebra in designing algorithms in graph streams. |
Latest revision as of 01:59, 7 March 2013
| 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.
