The first switching lemmas were proved in 1980ies and gave us lower bounds for the size of small-depth circuits. In particular they gave us optimal lower bounds for the size of circuits computing parity and proved that there are functions that have small circuits of depth d, but require (sub)-exponential size if the depth is restricted to d-1.

Some questions were left open in the 1980ies but have been resolved more recently. Two such questions are to establish sharp estimates for the best correlation with parity and to prove that the just mentioned hierarchy result can be established in an average case setting. Both these results used new variants of the switching lemma.

We survey these results and give an indication what modifications were needed to obtain the recent results.

If time permits we also discuss how yet other switching lemmas can be used to prove lower bounds for the length of Frege proofs using small-depth formulas.

Finding the connected components of a graph is one of the most basic graph problems. Although it is easy to find components sequentially using graph search or a disjoint set union algorithm, some important applications require finding the components of huge graphs, making sequential algorithms too slow. We describe recent progress on concurrent algorithms for this problem. Some simple algorithms seem surprisingly hard to analyze, and claims made in the literature about some of them are false.

This talk is organized in collaboration with the Collège de France.