Editing Open Problems:55
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| Line 5: | 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-06}}, by choosing elements of $D$ from $\ | + | 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. |
| β | '''Question | + | '''Question''': Find suitable applications of Clifford algebra in designing algorithms in graph streams. |
