On Approximating the Entropy of Polynomial Mappings

DSpace/Manakin Repository

On Approximating the Entropy of Polynomial Mappings

Citable link to this page

 

 
Title: On Approximating the Entropy of Polynomial Mappings
Author: Dvir, Zeev; Gutfreund, Dan; Rothblum, Guy N.; Vadhan, Salil P.

Note: Order does not necessarily reflect citation order of authors.

Citation: Dvir, Zeev, Dan Gutfreund, Guy N.Rothblum, and Salil Vadhan. 2011. On approximating the entropy of polynomial mappings. In Proceedings of the Second Symposium on Innovations in Computer Science (ICS 2011), January 7-9, 2011, Beijing, China, 460-475.
Full Text & Related Files:
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).
Published Version: http://conference.itcs.tsinghua.edu.cn/ICS2011/content/papers/28.html
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#OAP
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:33896773
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters