Longest Path Distance in Random Circuits

Source abstract

We study distance properties of a general class of random directed acyclic graphs ( dag s). In a dag , many natural notions of distance are possible, for there exist multiple paths between pairs of nodes. The distance of interest for circuits is the maximum length of a path between two nodes. We give laws of large numbers for the typical depth (distance to the root) and the minimum depth in a random dag . This completes the study of natural distances in random dag s initiated (in the uniform case) by Devroye and Janson. We also obtain large deviation bounds for the minimum of a branching random walk with constant branching, which can be seen as a simplified version of our main result.