zbMATH — the first resource for mathematics

On the depth of randomly generated circuits. (English) Zbl 1379.68182
Diaz, Josep (ed.) et al., Algorithms – ESA ’96. 4th annual European symposium, Barcelona, Spain, September 25–27, 1996. Proceedings. Berlin: Springer (ISBN 3-540-61680-2). Lecture Notes in Computer Science 1136, 208-220 (1996).
Summary: This research is motivated by the Circuit Value Problem; this problem is well known to be inherently sequential. We consider Boolean circuits with descriptions length \(d\) that consist of gates with a fixed fan-in \(f\) and a constant number of inputs. Assuming uniform distribution of descriptions, we show that such a circuit has expected depth \(O(\log d)\). This improves on the best known result. More precisely, we prove for circuits of size \(n\) their depth is asymptotically \(ef\) ln \(n\) with extremely high probability. Our proof uses the coupling technique to bound circuit depth from above and below by those of two alternative discrete time processes. We are able to establish the result by embedding the processes in suitable continuous time branching processes. As a simple consequence of our result we obtain that monotone CVP is in the class average NC.
For the entire collection see [Zbl 0855.00034].

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: DOI