Avi Wigderson: Elementary Mathematical Problems Disguising Computational Hardness

Abstract:  The theory of computation has done (and is doing) incredibly well on upper bounds - finding ingenious efficient algorithms for important problems. However, it had a pathetic and frustrating performance on lower bounds - the challenge of proving computational hardness of natural problems on general computational models.  In this talk I hope to popularize some approaches that would lead to such lower bounds, which can be encapsulated by clear, elementary mathematical problems from different areas (mostly algebraic, combinatorial and information-theoretic), which mostly do not seem computational at all. Some of these problems may be susceptible to known mathematical techniques, or inspire the creation of new ones. All of them can be understood by undergrads.