Markov models on trees arise naturally in many fields, notably in molecular biology - as models of evolution; in statistical physics - as models of spin systems; and in networking - as models of broadcasting. In this talk, I will discuss various inference problems motivated especially by applications in statistical phylogenetics, i.e. the reconstruction of evolutionary histories of organisms from their molecular sequences. In particular, I will consider the "root reconstruction" problem: how accurately can one guess the value at the root of the tree, given the state at the leaves? I will focus on recent work establishing new conditions for the impossibility of such reconstruction. I will also discuss the related "phylogenetic reconstruction" problem: given enough samples at the leaves, can one reconstruct the tree that generated this data and, if so, how efficiently? I will present a recent result on a sharp transition in the number of samples required to recover the tree topology, using a connection to the root reconstruction problem above. Time permitting, I will describe briefly connections to computational learning theory and network tomography as well. This is joint work with S. Bhamidi, C. Borgs, J. Chayes, C. Daskalakis, E. Mossel, and R. Rajagopal.