Advanced Topics in Computer Science: Meta-complexity and Cryptography
Description:
Meta-complexity refers to the computational complexity of problems that are themselves about computations and their complexity. Such problems include the Minimum Circuit Size Problem and the Time-bounded Kolmogorov Complexity Problem, the study of which originated in the 1950s/60s and predate the modern study of Complexity theory.
Meta-complexity provides a unifying framework for a variety of central tasks in several areas of computer science, including computational complexity, cryptography, and learning theory, and there has been a recent explosion of works connecting these areas through the lens of Meta-complexity. In this course, we will focus on these recent developments, with a particular focus on connections with Cryptography.
The course is taught in English and in-person from the Technion.
Additionally, there will be remote attendees via Zoom from Cornell University.
Technion students need to attend in person.
Learning outcomes:
By the end of the course, a student will be able to:
* Describe classic concepts, problems and key results in meta-complexity.
* Analyze algorithms and cryptographic schemes related to meta-complexity
* Explain reductions between meta-complexity and cryptographic problems.
Prerequisites: theory of computation, mathematical maturity.
Course Schedule: Mondays and Tuesdays from 16.30-19.30, during the dates of April 7-May 6
April 7,8: Class
April 14,15: No class (Pesach break)
April 21,22: Class
April 28,29: Class
May 5,6: Class
Course requirements: 2-3 homework problems sets, providing scribe notes (potentially in pairs) for one lesson.