A monotone planar circuit (MPC) is a Boolean circuit that can be
embedded in a plane, and that has only AND and OR
gates. Yang showed that the one-input-face
monotone planar circuit value problem (MPCVP) is in NC^2, and
Limaye et. al. improved the bound to ... more >>>

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