Carsten Damm, Markus Holzer, Pierre McKenzie

Tensor calculus over semirings is shown relevant to complexity

theory in unexpected ways. First, evaluating well-formed tensor

formulas with explicit tensor entries is shown complete for $\olpus\P$,

for $\NP$, and for $\#\P$ as the semiring varies. Indeed the

permanent of a matrix is shown expressible as ...
more >>>

Scott Aaronson

This paper introduces a new technique for removing existential quantifiers

over quantum states. Using this technique, we show that there is no way

to pack an exponential number of bits into a polynomial-size quantum

state, in such a way that the value of any one of those bits ...
more >>>