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]