We provide a general method for nding all natural operations on the Hochschild complex of E-algebras, where E is any algebraic structure encoded in a PROP with multiplication, as for example the PROP of Frobenius, commutative or A1-algebras. We show that the chain complex of all such natural operations is approximated by a certain chain complex of formal operations, for which we provide an explicit model that we can calculate in a number of cases. When E encodes the structure of open topological conformal eld theories, we identify this last chain complex, up quasi-isomorphism, with the moduli space of Riemann surfaces with boundaries, thus establishing that the operations constructed by Costello and Kontsevich-Soibelman via dierent methods identify with all formal operations. When E encodes open topological quantum eld theories (or symmetric Frobenius algebras) our chain complex identies with Sullivan diagrams, thus showing that operations constructed by Tradler-
Zeinalian, again by dierent methods, account for all formal operations. As an illustration of the last result we exhibit two innite families of non-trivial operations and use these to produce non-trivial higher string topology operations, which had so far been elusive.