9
$\begingroup$

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.

$\endgroup$

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.