Karp-Lipton theorems: Translating non-uniform `collapses' into uniform `collapses' (an exposition)

Oded's comments

I am recommending another insightful exposition of Roei.

The original abstract [revised slightly by me]

Assume that there exists an infinite sequence of small circuits, one for each input length, that solves some [supposedly] hard problem. Can we use this fact to construct a single efficient algorithm that solves some (possibly different) [supposedly] hard problem on all input lengths? This is the technical question that underlies many results that are typically referred to as Karp-Lipton theorems, following the classic result in this spirit by Karp and Lipton (1980). My goal in this text is to describe the various ideas that were introduced over the years to try and answer the question.

See Roei's expositions page.