Delay optimization of linear depth boolean circuits with prescribed input arrival times

We consider boolean circuits C   over the basis Ω={∨,∧}Ω={∨,∧} with inputs x1x1, x2,…,xnx2,…,xn for which arrival times t1,t2,…,tn∈N0t1,t2,…,tn∈N0 are given. For 1⩽i⩽n1⩽i⩽n we define the delay of xixi in C   as the sum of titi and the number of gates on a longest directed path in C   starting at xixi. The delay of C is defined as the maximum delay of an input.Given a function of the formf(x1,x2,…,xn)=gn−1(gn−2(…g3(g2(g1(x1,x2),x3),x4)…,xn−1),xn)f(x1,x2,…,xn)=gn−1(gn−2(…g3(g2(g1(x1,x2),x3),x4)…,xn−1),xn) where gj∈Ωgj∈Ω for 1⩽j⩽n−11⩽j⩽n−1 and arrival times for x1,x2,…,xnx1,x2,…,xn, we describe a cubic-time algorithm that determines a circuit for f over Ω that is of linear size and whose delay is at most 1.44 times the optimum delay plus some small constant.