CS 6816

Meta-Complexity and Cryptography

Course Description

Course information provided by the Courses of Study 2024-2025.

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 development, with a particular focus on connections with Cryptography.

When Offered Spring.

Permission Note Enrollment limited to: Cornell Tech PhD students.

• Describe classic problems, concepts, and key results, in meta-complexity.
• Analyze algorithms and cryptographic schemes related to meta-complexity.
• Explain reductions between meta-complexity and cryptographic problems.

View Enrollment Information