Boolean decision trees are perhaps the simplest model of boolean function computation. This model measures the cost of a computation entirely by the number of input bits that are accessed. There is a natural notion of a randomized decision tree, which makes use of randomness in choosing which input bits to look at. The influence of a particular input variable on a boolean function is the probability that, for a uniformly random assignment of the variables, flipping the input variable changes the value of the function. In this talk, I'll do a brief survey of decision tree complexity and present a new inequality which establishes a relationship between decision tree computation of an arbitrary boolean function and the influences of its variables. Combining this with another inequality due to Schramm and Steif, we deduce new lower bounds for randomized decision tree complexity. This is joint work with Ryan O'Donnell, Rocco Servedio and Oded Schramm.