In particular, we pursues lower bounds of a Boolean sum, that is a set of disjunctions of monotone variables. For monotone circuit complexity, we improved the known lower bound of an almost explicit Boolean sum. More precisely, we define a Boolean sum by shifting a set of variables, and show that almost all of such Boolean sums require the monotone complexity $\Omega(n^2/2^{O((\log\log n)^2)})$.
We also consider a circuit model that allows NOT gates but that has some other restriction. A general circuit that computes a Boolean sum can be naturally regarded as an (2-fanin) $\brace{\cup,\cap}$-circuit that computes the corresponding family of sets of variables. Here we restrict the alternation of $\cup$ and $\cap$, and the domain of set operations in $\brace{\cup,\cap}$-circuits. More specifically, we consider the following restriction: the alternation of $\cup$ and $\cap$ to be at most $O(1)$, and the cardinality of the common part of the input sets for every gate is at most $o(n)$. Under this restriction, we obtain non-linear lower bounds of the family of sets associated with almost $\Omega(\log n)$-wise independent random variables.
We also show that the multiplication is really harder than the addition in input wise synchronous circuits. Circuit depth is another important measure of complexity, and one interesting question is the depth of randomly generated circuits. We analyze the structure of random circuits, and determine the depth a size $n$ circuit is $2e \log_e n$, under the uniform distribution over the standard description of circuits. (This is the author's Thesis for the Doctor of Engineering.)