CS 6816 - Meta-Complexity and Cryptography

Spring. 3 credits. Letter grades only (no audit).

Enrollment limited to: Cornell Tech PhD Students. Offered in Cornell Tech in NYC.

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.