|
|
Dec 04, 2024
|
|
CS 6816 - Meta-Complexity and Cryptography Spring. 3 credits. Letter grades only (no audit).
Enrollment limited to: Cornell Tech PhD students. Offered in New York City at Cornell Tech.
R. Pass.
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.
Outcome 1: Describe classic problems, concepts, and key results, in meta-complexity.
Outcome 2: Analyze algorithms and cryptographic schemes related to meta-complexity.
Outcome 3: Explain reductions between meta-complexity and cryptographic problems.
Add to Favorites (opens a new window)
|
|
|