Tales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential Privacy
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore three recent results utilizing obfuscation to address open questions in theoretical computer science. Delve into the areas of bounded arithmetic, derandomization, metacomplexity, average-case complexity, and differential privacy. Examine the Circuit Range Avoidance problem and its implications for separating Cook's theory PV1 from Jeřábek's theory APC1. Investigate the NP-hardness of computing conditional time-bounded Kolmogorov complexity and its connection to eliminating Heuristica. Discover a novel task in differential privacy that is achievable with a computational adversary but impossible with an all-powerful one. Gain insights into the applications of indistinguishability obfuscation, differing inputs obfuscation, and keyless collision-resistant hash functions in solving longstanding theoretical problems.
Syllabus
Tales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential Privacy
Taught by
Simons Institute
Related Courses
Randomized Methods in ComplexityIndian Institute of Technology Kanpur via Swayam Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen
Institute for Advanced Study via YouTube Expander Graph Application 2: Derandomization - Lecture 16c of CS Theory Toolkit
Ryan O'Donnell via YouTube Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
Association for Computing Machinery (ACM) via YouTube High-Precision Estimation of Random Walks in Small Space
IEEE via YouTube