  We take a whirlwind tour of problems and techniques at the boundary of
computer science and statistical physics. We start with a brief description of
P, NP, and NP-completeness. We then discuss random graphs, including the
emergence of the giant component and the k-core, using techniques from
branching processes and differential equations. Using these tools as well as
the second moment method, we give upper and lower bounds on the critical clause
density for random k-SAT. We end with community detection in networks,
variational methods, the Bethe free energy, belief propagation, the
detectability transition, and the non-backtracking matrix.

Disordered Systems and Neural Networks;Statistical Mechanics;Computational Complexity;Physics and Society