Abstract:
Advisor: Prof. Amir Yehudayoff
Abstract:
In circuit complexity theory we classify Boolean functions according to the size of the
Boolean circuits that computes them. We are going to talk about a new matrix rank called
the "Blocky rank" which was defined not long ago and show how we can achieve a lower
bound on the size of 2-depth circuit that computes a function f by finding lower bound on
the Blocky rank. We will also discuss about general properties of this rank and computes the
rank for a Linear threshold function, which is a basic operator in our circuits. The Inner
product function was studied before in the context of circuit size and by using the blocky
rank we improve the known result.