circuit complexity course homework 1

prove that the circuit size complexity of $\text{[math]}$ (i.e. $\text{[math]}$ of $\text{[math]}$ bits) is at most $\text{[math]}$ . (you can discard $\text{[math]}$ gates.)

a lower bound of $\text{[math]}$ is given by parity_function.html, an upper bound (of the same size) can be shown by demonstrating a circuit that computes parity in the following manner:
broken link: xopp-figure:/home/mahmooz/brain/pen/2024-11-17-Note-09-35.xopp
in broken link: blk:fig-circ-comp-prb-1 we have for each adjacent pair of input nodes 5 extra intermediate nodes, we have a total of $\text{[math]}$ adjacent pairs of input nodes, and so the total number of nodes in the graph is $\text{[math]}$ . if we ignore $\text{[math]}$ gates, this reduces to $\text{[math]}$ .

prove that for every function $\text{[math]}$ we have $\text{[math]}$ .

show that a monotone circuit computes a monotone function.
show that every monotone function $\text{[math]}$ can be computed by a monotone circuit of size $\text{[math]}$ ( $\text{[math]}$ is possible too).

the proof for the first statement is almost trivial, we list each possible combination of inputs (each possible input pair) and check that for each two combinations $\text{[math]}$ , if $\text{[math]}$ , then for each function of $\text{[math]}$ , which are the basis functions for the monotone circuit model, we have:
$\text{[math]}$ the possible combinations are $\text{[math]}$ , in total we would have to make 16 comparisons, a few examples are:
$\text{[math]}$ the proof for the second statement seems to be a little more involved: for some boolean function $\text{[math]}$ , let $\text{[math]}$ be the smallest number such that $\text{[math]}$ , for each number $\text{[math]}$ such that $\text{[math]}$ , we construct a circuit with all AND gates whose inputs are from the input gates that correspond to the 1's in the binary representation of $\text{[math]}$ , said circuit will return 1 if the input matches $\text{[math]}$ or is some number greater than $\text{[math]}$ whose 1's are exactly those of $\text{[math]}$ 's with some extra 1's which means it will be a greater number (take any binary number, flip any bit from 0 to 1, it will become greater), since we do this for all numbers greater than $\text{[math]}$ , we can "combine" all of those circuits using OR gates, so that the input to the main circuit is directed to every such sub-circuit we construct, so that the main circuit will only output 1 if its input is greater than $\text{[math]}$ . this is exactly what we want because every monotone boolean function has to "flip" its outputs from 0 to 1 at some number $\text{[math]}$ and wouldnt return to outputting 0 again on higher numbers because otherwise it wouldnt be monotone. since we have shown a proper construction of a monotone circuit for each possible monotone function, we know that every monotone function can be computed by some monotone circuit. for each sub-circuit that we construct for some $\text{[math]}$ , we use at most $\text{[math]}$ intermediary AND gates, and since we have $\text{[math]}$ possible candidates for $\text{[math]}$ , we need at most $\text{[math]}$ such sub-circuits at the first intermediary layer, hence the first intermediary layer has $\text{[math]}$ vertices, the next layers will contribute an additional size that is $\text{[math]}$ , giving us a total complexity of $\text{[math]}$ .
notice that this is true for all functions except those that satisfy $\text{[math]}$ or $\text{[math]}$ , because there is no way to construct a function from $\text{[math]}$ that negates the input.

prove that for every $\text{[math]}$ , there exists some monotone function $\text{[math]}$ whose circuit complexity is $\text{[math]}$ .

see boolean_circuit.html.
this is the same as the argument in boolean_circuit.html with $\text{[math]}$ being the number of possible monotone functions. this number is given by approximation of dedekind numbers.

prove for every non-degenerated boolean function $\text{[math]}$ we have $\text{[math]}$ .

i think informally we can argue that since for a degenerated boolean function, the output should depend on all inputs, we must have atleast $\text{[math]}$ at each $\text{[math]}$ 'th layer in the circuit, and those add up to $\text{[math]}$ ( $\text{[math]}$ ).
let $\text{[math]}$ be the number of input gates, consider the geometric progression $\text{[math]}$ where $\text{[math]}$ , i.e. $\text{[math]}$ , its sum (by geometric_progression.html) is
$\text{[math]}$ we have $\text{[math]}$ gates in the entire circuit, if we remove the $\text{[math]}$ input gates we get $\text{[math]}$ intermediary gates.