YoVDO

Tales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential Privacy

Offered By: Simons Institute via YouTube

Tags

Obfuscation Courses Cryptography Courses Theoretical Computer Science Courses Differential Privacy Courses Derandomization Courses

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

Automata Theory
Stanford University via edX
Intro to Theoretical Computer Science
Udacity
Computing: Art, Magic, Science
ETH Zurich via edX
理论计算机科学基础 | Introduction to Theoretical Computer Science
Peking University via edX
Quantitative Formal Modeling and Worst-Case Performance Analysis
EIT Digital via Coursera