We show that the bipartite perfect matching problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.

We obtain our result by an almost complete ... more >>>

A black-white combinatorial game is a two-person game in which the pieces are colored either black or white. The players alternate moving or taking elements of a specific color designated to them before the game begins. A player loses the game if there is no legal move available for his ... more >>>

We consider the complexity of determining the winner of a finite, two-level poset game.
This is a natural question, as it has been shown recently that determining the winner of a finite, three-level poset game is PSPACE-complete.
We give a simple formula allowing one to compute the status ... more >>>

Abstract:We define and construct efficient depth-universal and almost-size-universal quantum circuits. Such circuits can be viewed as general-purpose simulators for central classes of quantum circuits and can be used to capture the computational power of the circuit class being simulated. For depth we construct universal circuits whose depth is the same ... more >>>

Higman showed that if A is *any* language then SUBSEQ(A)
is regular, where SUBSEQ(A) is the language of all
subsequences of strings in A. (The result we attribute
to Higman is actually an easy consequence of his work.)
Let s_1, s_2, s_3, ... more >>>

A set is called NP-simple if it lies in NP, and its complement is infinite, and does not contain any infinite subsets in NP. Hartmanis, Li and Yesha proved that no set which is hard for NP under many-one (Karp) reductions is NP-simple unless the intersection of NP and coNP ... more >>>

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 >>>

It is shown that determining whether a quantum computation
has a non-zero probability of accepting is at least as hard as the
polynomial time hierarchy. This hardness result also applies to
determining in general whether a given quantum basis state appears
with nonzero amplitude in a superposition, or whether a ... more >>>