As showed in the paper Monotone Circuits for the Majority Function, is possible to construct a monotone boolean circuit for the majority function on n variables with size O(n^3) and depth 5.3 log(n)+ O(1).http://link.springer.com/chapter/10.1007/11830924_38My question is, what is the time-complexity of such constrution? (i.e., the time needed to construct the circuit, given n in unary)
Circuity complexity: monotone circuit of Majority function
cc.complexity theory;circuit complexity;boolean functions;circuit depth