Description of Russell Impagliazzo's lectures at the
Fall school (Sept.'04)

Notions of Intractability

These lectures will compare various notions of intractability, i.e., when is a computational problem beyond the reach of solvability with a reasonable amount of resources? We get various notions of infeasibility by looking at different resource limits (e.g. super-polynomial or exponential), various models of computation (deterministic machines, probabilistic machines, or Boolean circuits), and various standards for success (worst-case decision, worst-case approximation, average-case decision, etc.). In these lectures, we will show relationships between various notions of intractability, e.g., when can a function with one type of intractability be used to construct a function with a seemingly stronger type of intractability?

We will then go on to consider the consequences of various notions of intractability for proof complexity, the power of randomized algorithms, and cryptography.