On Approximating the Entropy of Polynomial Mappings

We investigate the complexity of the following computational problem:

Polynomial Entropy Approximation (PEA): Given a low-degree polynomial mapping , where is a finite field, approximate the output entropy where is the uniform distribution on and may be any of several entropy measures.

We show:

• Approximating the Shannon entropy of degree 3 polynomials to within an additive constant (or even n^.9) is complete for SZKP_L, the class of problems having statistical zero-knowledge proofs where the honest verifier and its simulator are computable in logarithmic space. (SZKP_L contains most of the natural problems known to be in the full class SZKP.)
• For prime fields and homogeneous quadratic polynomials , there is a probabilistic polynomial-time algorithm that distinguishes the case that has entropy smaller than k from the case that has min-entropy (or even Renyi entropy) greater than (2 + o(1))k.
• For degree d polynomials , there is a polynomial-time algorithm that distinguishes the case that 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 has max-entropy at least (1 + o(1)) k^d (for fixed d and large k).