Polar codes have recently emerged as a new class of low-complexity codes achieving Shannon capacity. This talk introduces polar codes with emphasis on the probabilistic phenomenon underlying the code construction. New results and connections to randomness extraction for structured sources are discussed.
Computer Science and Discrete Mathematics (CSDM)
With the notion of interaction with oracles as a unifying theme of much of my dissertation work, I discuss novel models and results for property testing and computational learning, with the use of Fourier analytic and probabilistic methods.
A linear property of Banach spaces is called "local" if it depends on finite number of vectors and is invariant under renorming (i.e., distorting the norm by a finite factor). A famous theorem of Ribe states that local properties are invariant under (non linear) uniform-homeomorphisms, suggesting that local properties should have purely metric characterizations.
The Ribe program attempts to uncover explicit metric characterizations of local properties, and study them in the context of metric spaces. More broadly it attempts to apply ideas from Banach
We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. In particular, we show:
(1) The sparsity achieved by [Kane-Nelson, SODA 2012] in the sparse Johnson-Lindenstrauss lemma is optimal up to a log(1/eps) factor.
(2) RIP_2 matrices preserving k-space vectors in R^n with the optimal number of rows must be dense as long as k < n / polylog(n).