Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > APP:
Reports tagged with APP:
TR02-036 | 30th May 2002
Stephen A. Fenner

PP-lowness and a simple definition of AWPP

We show that the counting classes AWPP and APP [Li 1993] are more robust
than previously thought. Our results identify asufficient condition for
a language to be low for PP, and we show that this condition is at least
as weak as other previously studied criteria. Our results imply that
more >>>


TR24-052 | 15th March 2024
Justin Yirka

Even quantum advice is unlikely to solve PP

Revisions: 1

We give a corrected proof that if PP $\subseteq$ BQP/qpoly, then the Counting Hierarchy collapses, as originally claimed by [Aaronson, CCC 2006]. This recovers the related unconditional claim that PP does not have circuits of any fixed size $n^k$ even with quantum advice. We do so by proving that YQP*, ... more >>>




ISSN 1433-8092 | Imprint