# On approximating the entropy of polynomial mappings

### Citation:

Dvir, Zeev, Dan Gutfreund, Guy Rothblum, and Salil Vadhan. “On approximating the entropy of polynomial mappings.” In Proceedings of the Second Symposium on Innovations in Computer Science (ICS 2011), 460-475. Tsinghua University Press, 2011.
 ICS2011.pdf 309 KB ECCC2010.pdf 4.31 MB

### Abstract:

Version HistoryFull version posted as ECCC TR10-60.

We investigate the complexity of the following computational problem:

Polynomial Entropy Approximation (PEA): Given a low-degree polynomial mapping $$p : \mathbb{F}^n → \mathbb{F}^m$$, where F is a finite field, approximate the output entropy $$H(p(U_n))$$, where $$U_n$$ is the uniform distribution on $$\mathbb{F}^n$$ and $$H$$ may be any of several entropy measures.

We show:

• Approximating the Shannon entropy of degree 3 polynomials $$p : \mathbb{F}_2^n \to \mathbb{F}^m_2$$ over $$\mathbb{F}_2$$ to within an additive constant (or even $$n^.9$$) is complete for $$\mathbf{SZKP_L}$$, the class of problems having statistical zero-knowledge proofs where the honest verifier and its simulator are computable in logarithmic space. ($$\mathbf{SZKP_L}$$contains most of the natural problems known to be in the full class $$\mathbf{SZKP}$$.)

• For prime fields $$\mathbb{F} \neq \mathbb{F}_2$$ and homogeneous quadratic polynomials $$p : \mathbb{F}^n \to \mathbb{F}^m$$, there is a probabilistic polynomial-time algorithm that distinguishes the case that $$p(U_n)$$) has entropy smaller than k from the case that $$p(U_n))$$ has min-entropy (or even Renyi entropy) greater than $$(2 + o(1))k$$.

• For degree d polynomials $$p : \mathbb{F}^n_2 \to \mathbb{F}^m_2$$ , there is a polynomial-time algorithm that distinguishes the case that $$p(U_n)$$ has max-entropy smaller than $$k$$ (where the max-entropy of a random variable is the logarithm of its support size) from the case that $$p(U_n)$$ has max-entropy at least $$(1 + o(1)) \cdot k^d$$ (for fixed $$d$$ and large $$k$$).

Publisher's Version

Last updated on 06/30/2020