NOTES ON "FINDING CYCLES AND TREES IN SUBLINEAR TIME" (OUTLINE OF A SHORT PRESENTATION, FEB 2011) I'm talking of substructures (e.g., cycles) in graphs. Sublinear time refers to algorithms with direct access to the graph (can query the incidence function $f:V(G)\times[d]\to V(G)\cup\{\bot\}$) 1. Finding substructures (e.g., cycles) in sublinear time is possible only if the graph is "far" from lacking them (e.g., far from being cycle free). (Ow, cf., the $N$-cycle) 2. Finding substructures vs one-sided error (OSE) testing of the lack of these substructures; e.g., finding cycles vs *one-sided error* testers of cycle-freeness. The subgraph explored by a one-sided error tester *when it rejects* must contain such a substructure (e.g., a cycle), and thus the tester implicitly finds such a substructure. 3. Reducing cyclefreeness to bipartitness (since we have a one-sided error tester for the latter): A simple randomized reduction, open for deterministic. 4. The bipartite/cyclefree (one-sided error) tester: The special case of expander graphs. 5. Finding cycles of length at least four. A reduction to cyclefreeness, blow-ups the graph by $d^2$. Open: a direct algorithm (which is applicable for large $d$). 6. Finding trees: The cases of $k$-path and $k$-leaf tree. Open: Can you improve over the straightforward $k$-path finder, but note that the time complexity "must" be exponential in $k$. Finding a $k$-leaf tree by scanning $O(k/\eps)$ many vertices.