The major results in circuit complexity:
- Parity requires exponential-size circuits.
- For distinct primes p and q, there is no polynomial-size constant-depth circuit with AND, OR, NOT and Modp gates that can compute the Modq function.
- Clique and Matching do not have polynomial-size monotone circuits even with arbitrary depth.
- *NEXP does not have constant-depth circuits with Modm gates for any fixed m, prime or composite.
- The Complexity of Finite Functions by Ravi Boppana and Michael Sipser. A wonderful survey that covers definitions, results, proofs and references of the major circuit functions (except * which came after this survey).
- Nonuniform ACC Circuit Lower Bounds by Ryan Williams. This is the paper proving *.