Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with polarization:
TR18-015 | 25th January 2018
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett

Pseudorandom Generators from Polarizing Random Walks

Revisions: 1 , Comments: 1

We propose a new framework for constructing pseudorandom generators for $n$-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in $[-1,1]^n$. Next, we use a fractional pseudorandom generator as steps of a random walk in $[-1,1]^n$ that ... more >>>

TR18-027 | 8th February 2018
Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan

General Strong Polarization

Ar\i kan's exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix $M$, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the $\textit{polarization}$ of an associated $[0,1]$-bounded martingale, ... more >>>

ISSN 1433-8092 | Imprint