@conference {634337,
	title = {On approximating the entropy of polynomial mappings},
	booktitle = {Proceedings of the Second Symposium on Innovations in Computer Science (ICS 2011)},
	year = {2011},
	pages = {460-475},
	publisher = {Tsinghua University Press},
	organization = {Tsinghua University Press},
	abstract = {
	Version History:\&nbsp;Full version posted as ECCC TR10-60.



	We investigate the complexity of the following computational problem:



	Polynomial Entropy Approximation\&nbsp;(PEA): Given a low-degree polynomial mapping\&nbsp;\(p\&nbsp;:\&nbsp;\mathbb{F}^n\&nbsp;{\textrightarrow}\&nbsp;\mathbb{F}^m\), where\&nbsp;F\&nbsp;is a finite field, approximate the output entropy \(H(p(U_n))\), where\&nbsp;\(U_n\)\&nbsp;is the uniform distribution on\&nbsp;\(\mathbb{F}^n\)\&nbsp;and \(H\) may be any of several entropy measures.



	We show:



	
		
			Approximating the Shannon entropy of degree 3 polynomials\&nbsp;\(p : \mathbb{F}_2^n \to \mathbb{F}^m_2\)\&nbsp;over\&nbsp;\(\mathbb{F}_2\)\&nbsp;to within an additive constant (or even\&nbsp;\(n^.9\)) is complete for\&nbsp;\(\mathbf{SZKP_L}\), the class of problems having statistical zero-knowledge 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\&nbsp;\(\mathbf{SZKP}\).)
		
	
	
		
			For prime fields\&nbsp;\(\mathbb{F} \neq \mathbb{F}_2\)\&nbsp;and\&nbsp;homogeneous\&nbsp;quadratic polynomials\&nbsp;\(p : \mathbb{F}^n \to \mathbb{F}^m\), there is a probabilistic polynomial-time algorithm that distinguishes the case that\&nbsp;\(p(U_n)\)) has entropy smaller than\&nbsp;k\&nbsp;from the case that\&nbsp;\(p(U_n))\) has min-entropy (or even Renyi entropy) greater than \((2 + o(1))k\).
		
	
	
		
			For degree\&nbsp;d\&nbsp;polynomials\&nbsp;\(p : \mathbb{F}^n_2 \to \mathbb{F}^m_2\)\&nbsp;, there is a polynomial-time algorithm that distinguishes the case that\&nbsp;\(p(U_n)\) has\&nbsp;max-entropy\&nbsp;smaller than\&nbsp;\(k\)\&nbsp;(where the max-entropy of a random variable is the logarithm of its support size) from the case that\&nbsp;\(p(U_n)\) has max-entropy at least \((1 + o(1)) \cdot k^d\)\&nbsp;(for fixed\&nbsp;\(d\)\&nbsp;and large\&nbsp;\(k\)).
		
	

},
	url = {http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/28.html},
	author = {Zeev Dvir and Dan Gutfreund and Guy Rothblum and Salil Vadhan}
}
