Bounded indistinguishability for simple sources
summary
Shows both positive and negative Braverman-style claims: for constant-degree/local sources constant k suffices to fool simple distinguishers, and depth‑one, linear and quadratic sources need only polylog n or log log n k to fool DNFs or decision trees; yet constructs root-n-wise indistinguishable simple sources of degree O(log n) that the R function separates. Key tools are LP duality and Nisan–Szegedy approximate‑degree barriers, Razborov–Smolensky randomized polynomial approximations, sampling-by‑decision‑trees and LDPC code barriers; the constructions preserve indistinguishability and yield concrete separations.
AI-written summary · about
chapters (8)
- 0:00Start
- 0:58Introduction
- 11:13Motivation
- 15:33Braverman's Theorem for indistinguishable simple sources
- 20:09Web of Conjectures
- 27:01Overview of Results k-wise indistinguishable simple source distributions that fool
- 27:47OR, can distinguish Vn-wise indistinguishable simple source
- 33:13Summary Conclusion
related talks
01h 26mObfuscation 1
46mIndistinguishability Obfuscation from Bilinear Maps and LPN Variants
57mIndistinguishability Obfuscation from Well-Founded Assumptions
49mLower Bounds on the Overhead of Indistinguishability Obfuscation
01h 08mExpedition to Obfustopia: Indistinguishability Obfuscation from Well-Studied Assumptions to New...
46mOn Low End Obfuscation and Learning
48mTales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential Privacy
58mObfuscation 2