#### Milestone Year

### 1990

#### Linear lower bound on depth of Monotone circuits for Matching

Can the use of negation speed-up parallel computation,
let alone of natural computational problems?

A dramatic affirmative answer was provided by a WIS scientist
and his collaborator.
Referring to the problem of finding a large matching in a given graph,
they showed that parallel computations that do not use negation use
exponentially more time than parallel computations that use negation.