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.
Update April 12: Given the current situation, classes will be given on Zoom also for Technion students until further notice; if Technion classes resume to in person, so will this course.
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 Wed from 16.30-19.30, during the dates of April 13-May 4
March 25,30: class [Cancelled due to the war]
[April 1,6,8: Pesach break]
April 13,15: class
April 20: class (April 22, no class due to Yom Haatzmaut)
April 27,29: class
May 4: class
Zoom Link: https://cornell.zoom.us/j/92998337881?pwd=4GgdBhjjGPATU8XMV6yx1J2KwGCYEn.1
Course requirements: 2 homework problems sets.