# On Approximating the Entropy of Polynomial Mappings

Zeev Dvir, Dan Gutfreund, Guy Rothblum, and Salil Vadhan

### Abstract

We investigate the complexity of __Polynomial Entropy Approximation (PEA):__ Given a low-degree polynomial mapping p : F^n-> F^m, where F is a finite field, approximate the output entropy H(p(U_n)), where U_n is the uniform distribution on F^n and H may be any of several entropy measures.

We show:

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

- For prime fields F\neq F_2 and
*homogeneous* quadratic polynomials p : F^n->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 : F_2^n->F_2^m, 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))k^d (for fixed d and large k).

### Versions

- To appear in the
*Proceedings of the Second Symposium on Innovations in Computer Science (ICS 2011)*, Beijing, China, 7-9 January 2011. [pdf]
*Electronic Colloquium on Computational Complexity *TR10-60, October 2010. [pdf][ECCC page]

[ back to
Salil Vadhan's research]