Courses of Study 2024-2025 
    
    Dec 04, 2024  
Courses of Study 2024-2025
Add to Favorites (opens a new window)

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)