Satisfaction and optimization problems subject to random constraints are a well-studied area in the theory of computation. These problems also arise naturally in combinatorics, in the study of sparse random graphs. While the values of limiting thresholds have been conjectured for many such models, few have been rigorously established. In this context we study the size of maximum independent sets in random d-regular graphs. We show that for d exceeding an absolute constant, there exist explicit constants (a,c) depending on d such that the maximum size has constant fluctuations around (an - c(log n)), establishing the one-step replica symmetry breaking heuristics developed by statistical physicists. As an application of our method we also prove an explicit satisfiability threshold in random regular k-NAE-SAT. This is joint work with Jian Ding and Allan Sly.