Description of Russell Impagliazzo's lectures at the
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?
Fall school (Sept.'04)
Notions 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.