The perfect matching problem is known to
be in P, in randomized NC, and it is hard for NL.
Whether the perfect matching problem is in NC is one of
the most prominent open questions in complexity
theory regarding parallel computations.

Grigoriev and Karpinski studied the perfect matching problem
more >>>

A number of recent results have constructed randomness extractors
and pseudorandom generators (PRGs) directly from certain
error-correcting codes. The underlying construction in these
results amounts to picking a random index into the codeword and
outputting $m$ consecutive symbols (the codeword is obtained from
the weak random source in the case ... more >>>

A q-query Locally Decodable Code (LDC) encodes an n-bit message
x as an N-bit codeword C(x), such that one can
probabilistically recover any bit x_i of the message
by querying only q bits of the codeword C(x), even after
some constant fraction of codeword bits has been corrupted.

We give ... more >>>