Fast construction of straight line programs? Given a group $G$ and a set of generators $A$, we can ask ourselves (and do ask ourselves all the time) to bound the diameter of $G$ with respect to $A$. The diameter, let us recall, is defined to be the least $k$ such that every element $g$ of $G$ can be written as a product $x_1 x_2 \dotsc x_k$, $x_i \in A \cup \{e\}$. We care not just about the diameter, but also about navigation: that is, given $A$ and $g$, we would like to actually find a product $g = x_1 x_2 \dotsc
x_j$, $x_i \in A \cup \{e\}$, as quickly as possible.
Now, a product is a very special kind of straight-line program. What is known (for different interesting groups $G$) on the following question: given $A$ and $g$, can we construct quickly a (short) straight-line program that, starting from the elements of $A$, outputs $g$ quickly?
 A: Larsen, Michael. Navigating the Cayley graph of ${\rm SL}_2(\Bbb F_p)$.
Int. Math. Res. Not. 2003, no. 27, 1465–1471.
Math Review by Tullio G. Ceccherini-Silberstein: 
Consider the group ${\rm SL}_2(\Bbb F_p)$ with the generating system $$X=\left\{\left(\begin{matrix} 1&1\\ 0&1\end{matrix}\right),\ \left(\begin{matrix} 1&0\\ 1&1\end{matrix}\right)\right\}$$ The diameter of the Cayley graph $X(p)={\rm Cay}({\rm SL}_2(\Bbb F_p), X)$ is $O(\log p)$ [see A. Lubotzky, Discrete groups, expanding graphs and invariant measures, Progr. Math., 125, Birkhäuser, Basel, 1994; MR1308046 (96g:22018)]: there are two proofs of this fact, both non-constructive. The first one is based on bounding the eigenvalues of the combinatorial Laplacian on $L^2(X(p))$ away from zero; the second one uses the circle method to show that every element in ${\rm {\rm SL}}_2(\Bbb F_p)$ lifts to an element of ${\rm SL}_2(\Bbb Z)$ which has a short word representation [A. Lubotzky, R. S. Phillips and P. C. Sarnak, Combinatorica 8 (1988), no. 3, 261–277; MR0963118 (89m:05099)]. Lubotzky asked for an algorithm producing short word representations of general elements of ${\rm SL}_2(\Bbb F_p)$. In this paper such an algorithm is presented, but for word representations of length $O(\log p \log \log p)$ (rather than $O(\log p)$).
   More precisely one has the following theorem. There exist constants $c_1$ and $c_2$ such that for any $c_3 < 1$, there exists $c_4$ such that for any prime $p$ and any element in ${\rm SL}_2(\Bbb F_p)$, the algorithm will find a word of length $\leq c_1 \log p \log \log p$ in time $\leq c_4 \log^{c_2} p$ with probability $\geq c_3$.
