The fundamental difference between depth and delay

Earlier, it was proved that even for a minimal circuit the delay $T$ could be much less than the depth $D$. Namely, an infinite sequence of minimal circuits was constructed such that $T<\log_2D+6$ and $D\to\infty$. This result would be more interesting if the inequality were true for all equivalent minimal circuits. In this paper, we present an infinite sequence of Boolean functions $F_k$, $k=1,2,\dots$, such that any minimal circuit for an arbitrary function $F_k$ has the depth and the delay obeying the inequality $T<\log_2D+14$.
This research was supported by the Program of Basic Research of Department of Applied Mathematics of Russian Academy of Sciences “Algebraic and Combinatorial Methods of Mathematical Cybernetics”, project “Design and Complexity of Control Systems”.