ICS 2011

Welcome to ICS2011
Innovations in Computer Science  ICS 2011, Tsinghua University, Beijing, China, January 79, 2011. Proceedings, 460475, 9787302245179
Tsinghua University Press
We investigate the complexity of the following computational problem: Polynomial Entropy Approximation (PEA): Given a lowdegree 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 zeroknowledge 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 polynomialtime algorithm that distinguishes the case that p(Un) has entropy smaller than k from the case that p(Un) has minentropy (or even Renyi entropy) greater than (2 + o(1))k. • For degree d polynomials p : Fn2 → Fm2 , there is a polynomialtime algorithm that distinguishes the case that p(Un) has maxentropy smaller than k (where the maxentropy of a random variable is the logarithm of its support size) from the case that p(Un) has maxentropy at least (1 + o(1)) · kd (for fixed d and large k). Preview:

Copyright 20102011, Institute for Computer Science, Tsinghua University, All Rights Reserved.