The Turing and many-one completeness notions for $\NP$ have been
previously separated under {\em measure}, {\em genericity}, and {\em
bi-immunity} hypotheses on NP. The proofs of all these results rely
on the existence of a language in NP with almost everywhere hardness.

In this paper we separate the same NP-completeness ... more >>>

We show necessary and sufficient conditions that
certain algebraic functions like the rank or the signature
of an integer matrix can be computed in GapL.

more >>>

We initiate the study of quantifying the quantumness of
a quantum circuit by the number of gates that do not preserve
the computational basis, as a means to understand the nature
of quantum algorithmic speedups.
Intuitively, a reduction in the quantumness requires
an increase in the amount of classical computation, ... more >>>