  This chapter provides a hands-on tutorial on the important technique known as
self-reducibility. Through a series of "Challenge Problems" that are theorems
that the reader will---after being given definitions and tools---try to prove,
the tutorial will ask the reader not to read proofs that use self-reducibility,
but rather to discover proofs that use self-reducibility. In particular, the
chapter will seek to guide the reader to the discovery of proofs of four
interesting theorems---whose focus areas range from selectivity to information
to approximation---from the literature, whose proofs draw on self-reducibility.
  The chapter's goal is to allow interested readers to add self-reducibility to
their collection of proof tools. The chapter simultaneously has a related but
different goal, namely, to provide a "lesson plan" (and a coordinated set of
slides is available online to support this use [Hem19]) for a lecture to a
two-lecture series that can be given to undergraduate students---even those
with no background other than basic discrete mathematics and an understanding
of what polynomial-time computation is---to immerse them in hands-on proving,
and by doing that, to serve as an invitation to them to take courses on Models
of Computation or Complexity Theory.

Computational Complexity