PreviousNext

__
TR20-172
| 13th November 2020
__

Venkatesan Guruswami, Chaoping Xing#### Optimal rate list decoding over bounded alphabets using algebraic-geometric codes

__
TR20-171
| 12th November 2020
__

Russell Impagliazzo, Sam McGuire#### Comparing computational entropies below majority (or: When is the dense model theorem false?)

__
TR20-170
| 9th November 2020
__

Max Hopkins, Tali Kaufman, Shachar Lovett#### High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games

PreviousNext

Venkatesan Guruswami, Chaoping Xing

We construct two classes of algebraic code families which are efficiently list decodable with small output list size from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The alphabet size depends only on $\epsilon$ and is nearly-optimal.

The ... more >>>

Russell Impagliazzo, Sam McGuire

Computational pseudorandomness studies the extent to which a random variable $\bf{Z}$ looks like the uniform distribution according to a class of tests $\cal{F}$. Computational entropy generalizes computational pseudorandomness by studying the extent which a random variable looks like a \emph{high entropy} distribution. There are different formal definitions of computational entropy ... more >>>

Max Hopkins, Tali Kaufman, Shachar Lovett

Higher order random walks (HD-walks) on high dimensional expanders have played a crucial role in a number of recent breakthroughs in theoretical computer science, perhaps most famously in the recent resolution of the Mihail-Vazirani conjecture (Anari et al. STOC 2019), which focuses on HD-walks on one-sided local-spectral expanders. In this ... more >>>

PreviousNext