Combinatorial statistics deals with estimation of discrete parameters where the goal is to reconstruct the parameters exactly using explicit bounds on the number of samples needed, the running time of the estimation procedure and the estimation accuracy. I will discuss some recent work in this area including estimation of Markov random fields and estimation of "noisy" rankings.