A growing collection of my own surveys and notes, alongside recommendations of other writing I’ve found valuable. Entries marked Mine are my own.
Bounded arithmetic (or feasible mathematics) corresponds to mathematical theories relying on concepts only from a complexity class, ranging from AC⁰, P, PSPACE, and even beyond.
A gentle introduction to Cook’s theory PV targeting to computer scientists. Compared to existing textbooks, it features an informal definition of PV based on three postulates, which captures the high-level intuition, as well as a careful roadmap from axioms to formalizations of complicated mathematics.
A recent comprehensive survey on unprovability results in bounded arithmetic.
The comprehensive reference for proof complexity and bounded arithmetic — a standard textbook to reach for when you want a full picture of the field.
The Range Avoidance problem asks for a string outside the range of a given stretching circuit, like finding water in the ocean. Apparently, it is not an easy task.
An overview of this research direction and its connections to fundamental questions in derandomization and circuit complexity.
Catalytic computing studies space-bounded computation that may borrow a large, full memory, provided its contents are restored by the end. How can it be useful?
An accessible survey of catalytic computing, with a great collection of open problems.