**Expositions**

This page will contain a collection of notes that describe and explain known results. These are typically slightly-more-polished versions of texts that I wrote to myself and/or to friends, and that I'm putting online in the hope and belief that they can also be useful to others. While the texts describe results that were proved by others, all the mistakes are solely mine. (Of course, if you find such a mistake, I'll appreciate it if you send me a quick email about it.)

**Non-trivial derandomization implies weak lower bounds: An (almost) elementary proof**

Ryan Williams' fundamental result asserts that any non-trivial derandomization of a circuit class C implies weak lower bounds for C. This text presents an alternative (known) argument, in which C is separated from the class E^{NP} (rather than from the class NEXP, as in the original result). The proof is short, almost completely self-contained, and applies to more classes C than the original result.

A step-by-step review of the proof that polylog-wise independent distributions fool AC0. The text starts from Bazzi's proof framework, and tries to articulate exactly what we need (and are trying to do) in each step, while abstracting some general parts of the proof. The presentation of Braverman's proof is somewhat non-standard, relying on the notion of randomized tests.

A notable line of research in low-level complexity in the last decade deals with polynomial lower bounds for circuits of small depth solving subgraph isomorphism. Since the problem is NP-complete, the hope is that these lower bounds can be extended to large classes (e.g., to NC1). The text is an overview of a key result in this context, and is intended to be as simple and self-contained as possible.