All reports by Author Harm Derksen:

__
TR22-132
| 18th September 2022
__

Harm Derksen, Emanuele Viola#### Fooling polynomials using invariant theory

__
TR22-091
| 2nd July 2022
__

Harm Derksen, Emanuele Viola#### Quasirandom groups enjoy interleaved mixing

Harm Derksen, Emanuele Viola

We revisit the problem of constructing explicit pseudorandom generators

that fool with error $\epsilon$ degree-$d$ polynomials in $n$ variables

over the field $F_q$, in the case of large $q$. Previous constructions

either have seed length at least $2^{d}\log q$, and thus are only non-trivial

when the degree is less than ...
more >>>

Harm Derksen, Emanuele Viola

Let $G$ be a group such that any non-trivial representation has dimension

at least $d$. Let $X=(X_{1},X_{2},\ldots,X_{t})$ and $Y=(Y_{1},Y_{2},\ldots,Y_{t})$

be distributions over $G^{t}$. Suppose that $X$ is independent from

$Y$. We show that for any $g\in G$ we have

\[

\left|\mathbb{P}[X_{1}Y_{1}X_{2}Y_{2}\cdots X_{t}Y_{t}=g]-1/|G|\right|\le\frac{|G|^{2t-1}}{d^{t-1}}\sqrt{\mathbb{E}_{h\in G^{t}}X(h)^{2}}\sqrt{\mathbb{E}_{h\in G^{t}}Y(h)^{2}}.

\]

Our results generalize, improve, and ...
more >>>