Title:
|
On the depth of randomly generated circuits
|
Author:
|
Tsukiji, Tatsuie; Xhafa Xhafa, Fatos
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
Abstract:
|
This research is motivated by the Circuit Value Problem; this problem is well known to be inherently sequential. We consider Boolean Circuits with descriptions of 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 |
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Circuit value problem -Boolean circuits -Coupling technique -CVP -NC |
Rights:
|
|
Document type:
|
Article - Submitted version Report |
Share:
|
|