Tata Institute of Fundamental Research
Structure in the Theory of Computing: Algorithms, Randomness, Cryptography, Hardness
STCS Distinguished Lecture
Speaker:
Avi Wigderson (School of Mathematics
Institute for Advanced Study
Princeton, New Jersey)
Organiser:
Prahladh Harsha
Date:
Thursday, 29 Oct 2015, 16:00 to 17:00
Venue:
AG-66 (Lecture Theatre)
(Scan to add to calendar)
Abstract:
The world around us, including nature, society, science and mathematics, presents us with a large number and variety of computational problems. For each we seek solutions that minimize various resources while maintaining other desirable properties. The Theory of Computation is charged with figuring out the feasibility and costs of this multitude of problems. The past few decades of work have revealed remarkable structure: this complex world of problems, resources and properties clusters into a few natural groups which furthermore have conceptual meaning. I will survey some important aspects of this body of work, including: the tools of reduction and completeness, the reasons for clustering (which go to the very definition of computation by Turing), and the major challenges for a better understanding of this universe.
| Speaker: | Avi Wigderson (School of Mathematics Institute for Advanced Study Princeton, New Jersey) |
| Organiser: | Prahladh Harsha |
| Date: | Thursday, 29 Oct 2015, 16:00 to 17:00 |
| Venue: | AG-66 (Lecture Theatre) |
(Scan to add to calendar)
Abstract:
The world around us, including nature, society, science and mathematics, presents us with a large number and variety of computational problems. For each we seek solutions that minimize various resources while maintaining other desirable properties. The Theory of Computation is charged with figuring out the feasibility and costs of this multitude of problems. The past few decades of work have revealed remarkable structure: this complex world of problems, resources and properties clusters into a few natural groups which furthermore have conceptual meaning. I will survey some important aspects of this body of work, including: the tools of reduction and completeness, the reasons for clustering (which go to the very definition of computation by Turing), and the major challenges for a better understanding of this universe.