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 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 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)) kd (for fixed d and large k).

By: Zeev Dvir; Dan Gutfreund; Guy N. Rothblum; Salil Vadhan

Published in: H-0293 in 2010


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .