Caterina De Bacco - Max Planck Institute for Intelligent Systems In the last years, we have seen increased efforts of statistical physicists to tackle the evolution of stochastic dynamical processes in homogeneous and heterogeneous networks. While exact solutions are limited to very simple homogeneous and low dimensional models, like the Glauber dynamics of the 1D Ising model and a few other examples, in general the only available tools are numerical simulations or dynamical mean field theories with various degrees of sophistication. If one focuses on the description of the transient dynamics, far-from-equilibrium, the description is characterized by an exponential computational complexity in the duration of the process that prevents to tackle the problem in his general setting. As a consequence its study has been limited to either irreversible dynamics or by recurring to approximate methods that fail to capture the transient part of the dynamics. Here we show how matrix product states can help, by combining it with a dynamic message-passing algorithm (or cavity method). This unusual combination of statistical formalisms allows to effectively approximate a dynamical process on networks were variables evolve through parallel updates, by reducing the computational complexity from exponential to polynomial in both system size and duration in time.