This course teaches learners how to utilize XOR Lemmas to create resilient functions against polynomials. The main goal is to understand and apply an XOR lemma for resilient functions, along with a new structural result for low-degree polynomials. The course covers the known results, motivation, main result, and proof of the XOR lemma. The teaching method involves presenting theoretical concepts and proofs. This course is intended for individuals interested in cryptography, computer science, or mathematics.
XOR Lemmas for Resilient Functions Against Polynomials
Association for Computing Machinery (ACM) via YouTube
Overview
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
Taught by
Association for Computing Machinery (ACM)
