Extractors have the following property: For a random variable $X$ of min-entropy $k$ and a seed $Y$, denote the output of an $(k,\epsilon)$-extractor by $\mathrm{Ext}(X,Y)$. Then $\|\mathrm{Ext}(X,Y)-U\|_1\leq \epsilon$ where $U$ is the uniform distribution. View the distribution of $X$ as an vector where the value of an entry indexed by $x$ equals $\Pr[X=x]$, then the vector has $\ell_1$ norm $1$. And $\mathrm{Ext}(X,Y)-U$ as a vector, has $\ell_1$ norm at most $\epsilon$.

Expanders have a similar property but for $\ell_2$ norm: Let $A$ be the normalized adjacent matrix of an expander with $\lambda$ the second largest eigenvalue in absolute value. Then $\|Af-f^\parallel\|_2\leq \lambda$ for a vector $f$ of $\ell_2$ norm 1. Here $f^\parallel$ denotes the component of $f$ parallel to $\vec{1}$.

My question is: are there explicit pseudorandom objects with analogous properties (i.e., shrinking the "non-uniformly-distributed" component) for $\ell_p$ norms where $p>2$? More specifically, I am looking for such a property: given a vector $f$ of $\ell_p$ norm 1 as the input, the $\ell_p$-distance between $f^\parallel$ and the output of such objects should be bounded.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.