Advances in Boolean Function Analysis — Pseudorandom Generators from Polarizing Random Walks

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=t245APAI-Ps


Duration: 1:06:49
615 views
14

Pooya Hatami (Ohio State University)
https://simons.berkeley.edu/events/boolean-6
Advances in Boolean Function Analysis

This talk is concerned with a new framework for constructing pseudorandom generators (PRGs) for n-variate Boolean functions. The framework relies on two notions. First is a generalization of PRGs
called a fractional PRG, which is a pseudorandom distribution taking values in [-1,1]^n. Next, we show that a fractional PRG that satisfies certain nontriviality conditions can be used as steps to a polarizing random walk that converges to {-1,1}^n quickly. This allows us to reduce the task of constructing PRGs to constructing fractional PRGs.

We will demonstrate the power of this framework by constructing fractional PRGs from various bounds on the Fourier coefficients of a family of Boolean functions.

This talk is based on joint work with Eshan Chattopadhyay, Kaave Hosseini, and Shachar Lovett.



Other Videos By Simons Institute for the Theory of Computing


2020-08-25Sketching High-Dimensional Data
2020-08-24Remarks on the Discrete Cube
2020-08-24Crash Course on Probabilistically Checkable Proofs (PCP): Optimal Inapproximability Results
2020-08-21Sketching High-Dimensional Data
2020-08-21Remarks on the Discrete Cube
2020-08-21Crash Course on Probabilistically Checkable Proofs (PCP): Parallel Repetition
2020-08-20Remarks on the Discrete Cube
2020-08-20Crash Course on Probabilistically Checkable Proofs (PCP)...
2020-08-19Remarks on the Discrete Cube
2020-08-19Advances in Boolean Function Analysis — Pseudorandom Generators from Polarizing Random Walks - 2
2020-08-19Advances in Boolean Function Analysis — Pseudorandom Generators from Polarizing Random Walks
2020-08-19Crash Course on Probabilistically Checkable Proofs (PCP): Introduction
2020-08-12KKL via Random Restrictions
2020-08-12KKL via Random Restrictions
2020-08-07Concentration Inequalities for Boolean Functions via Pathwise Stochastic Analysis
2020-08-05Concentration Inequalities for Boolean Functions via Pathwise Stochastic Analysis 2
2020-08-04Deep “Internal” Learning - Deep Learning with Zero Examples
2020-08-04From Chaos to Information - Communication in a Crowd of Bats
2020-08-04Foundations of Early Human Learning
2020-08-04Interpreting Natural Language Processing Models
2020-08-03Sperm Whale Communication: What we know so far/ Understanding Whale Communication: First steps


Tags:
Simons Institute
Theory of Computing
Theory of Computation
Theoretical Computer Science
Computer Science
UC Berkeley
Advances in Boolean Function Analysis
Pooya Hatami