Arguments of Proximity

Explore the concept of Arguments of Proximity in this 22-minute conference talk. Delve into outsourcing computation in sublinear time and sublinear-time verification. Learn about Interactive Proof of Proximity (IPP) and its application to bounded depth computation. Discover the speaker's results, including 1-round arguments for P and lower bounds. Gain insights into the intuition behind IPP lower bounds. This concise yet informative presentation covers key aspects of proximity arguments and their implications in computational complexity theory.

Intro
Outsourcing Computation in Sublinear Time
Sublinear-time Verification
Interactive Proof of Proximity (IPP)
IPP for Bounded Depth Computation
Our Results in a Nutshell
Argument of Proximity
2-Round Arguments of Proximity
Result 1: 1-Round Arguments for P
Result 2: Lower Bounds
IPP Lower Bound: Intuition
Summary