On SZK and PP
Authors:
Preprint
Abstract
In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] and earlier communication complexity separations of Klauck [Kla11] and Razborov and Sherstov [RS10]. In addition, our results imply an oracle relative to which the class NISZK is not contained in PP. This answers an open question of Watrous from 2002 [Aar]. The technical core of our result is a stronger hardness amplification theorem for approximate degree, which roughly says that composing the gapped-majority function with any function of high approximate degree yields a function with high threshold degree. Using our techniques, we also give oracles relative to which the following two separations hold: perfect zero knowledge (PZK) is not contained in its complement (coPZK), and SZK (indeed, even NISZK) is not contained in PZK (indeed, even HVPZK). Along the way, we show that HVPZK is contained in PP in a relativizing manner. We prove a number of implications of these results, which may be of independent interest outside of structural complexity. Specifically, our oracle separation implies that certain parameters of the Polarization Lemma of Sahai and Vadhan [SV03] cannot be much improved in a black-box manner. Additionally, it implies new lower bounds for property testing algorithms with error probability arbitrarily close to 1/2. Finally, our results imply that two-message protocols in the streaming interactive proofs model of Cormode et al. [CTY11] are surprisingly powerful in the sense that, with just logarithmic cost, they can compute functions outside of UPP^CC.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- On the Impossibility of Entropy Reversal, and Its Application to Zero-Knowledge Proofs2017
- How to Achieve Perfect Simulation and a Complete Problem for Non-interactive Perfect Zero-KnowledgeJournal of Cryptology, 2013
- The Sign-Rank of AC$^0$SIAM Journal on Computing, 2010
- Complexity measures of sign matricesCombinatorica, 2007
- A linear lower bound on the unbounded error probabilistic communication complexityJournal of Computer and System Sciences, 2002
- Perceptrons, PP, and the polynomial hierarchycomputational complexity, 1994
- PP is as Hard as the Polynomial-Time HierarchySIAM Journal on Computing, 1991
- Relativized perfect zero knowledge is not BPPInformation and Computation, 1991
- Statistical zero-knowledge languages can be recognized in two roundsJournal of Computer and System Sciences, 1991
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989