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

by Roei Tell

#### 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.

Back to
list of Oded's choices.