Computer Science/Discrete Mathematics

Random walks on a graph, and Markov chains in general, provide endless fascination and myriad applications (for example, in sampling and approximation algorithms.)  A nearly trivial but endlessly useful tool in this theory is the "harmonic lemma for...

A cornerstone result in complexity theory is that O(1)-depth circuits with unbounded fan-in AND/OR gates computing the parity of an n bit string must have exp(n) size. Two completely different proofs of this are known, both dating back to the 1980's...