Citation:
ICS2011.pdf  309 KB  
ECCC2010.pdf  4.31 MB 
Abstract:
Version History: Full version posted as ECCC TR1060.
We investigate the complexity of the following computational problem:
Polynomial Entropy Approximation (PEA): Given a lowdegree 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 zeroknowledge 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 polynomialtime algorithm that distinguishes the case that \(p(U_n)\)) has entropy smaller than k from the case that \(p(U_n))\) has minentropy (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 polynomialtime algorithm that distinguishes the case that \(p(U_n)\) has maxentropy smaller than \(k\) (where the maxentropy of a random variable is the logarithm of its support size) from the case that \(p(U_n)\) has maxentropy at least \((1 + o(1)) \cdot k^d\) (for fixed \(d\) and large \(k\)).