ICS 2011

Welcome to ICS2011

Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 460-475, 978-7-302-24517-9
Tsinghua University Press

On Approximating the Entropy of Polynomial Mappings Authors : Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan [Download PDF]

Abstract:
We investigate the complexity of the following computational problem:
Polynomial Entropy Approximation (PEA): Given a low-degree polynomial mapping p : Fn → Fm, where F is a finite field, approximate the output entropy H(p(Un)), where Un is the uniform distribution on Fn and H may be any of several entropy measures.
We show:
• Approximating the Shannon entropy of degree 3 polynomials p : Fn2 → Fm2 over F2 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 ≠ F2 and homogeneous quadratic polynomials p : Fn → Fm, there is a probabilistic polynomial-time algorithm that distinguishes the case that p(Un) has entropy smaller than k from the case that p(Un) has min-entropy (or even Renyi entropy) greater than (2 + o(1))k.
• For degree d polynomials p : Fn2 → Fm2 , there is a polynomial-time algorithm that distinguishes the case that p(Un) 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(Un) has max-entropy at least (1 + o(1)) · kd (for fixed d and large k).

Preview: