Some operations over Boolean functions are considered. It is shown that the operation of the geometrical projection and the operation of the monotone extension can increase the complexity of Boolean functions for formulas in each finite basis, for switching networks, for branching programs, and read-$k$-times branching programs, where $k\ge 2$. ... more >>>

We prove that any monotone switching network solving directed connectivity on $N$ vertices must have size $N^{\Omega(\log N)}$ more >>>