XOR Lemmas for Resilient Functions Against Polynomials

Explore the concept of XOR Lemmas for resilient functions against polynomials in this 28-minute ACM conference talk. Delve into known results, motivations, and the main findings, including a new XOR lemma for resilient functions. Examine the key tool of a novel structural result for low-degree polynomials and its application in correlation bounds. Follow the proof of the XOR lemma derived from the structural result, and gain insights into the proof of the structural result itself. Conclude with a comprehensive summary of the presented concepts and their implications in the field of computing and mathematics.

Syllabus

Intro
Outline
Introduction
Known results: XOR Lemmas
Third motivation
Main result: an XOR lemma for resilient functions
Main tool: A new structural result for low-degree polynomials
From the structural result to the correlation bound
Proof of XOR lemma from structural result
Proof of Structural result
Summary