M.Sc. Graduation Seminar: On Blocky rank of matrices

M.Sc. Graduation Seminar: On Blocky rank of matrices

M.Sc. Graduation Seminar: On Blocky rank of matrices

Monday, May 29, 2023
  • Lecturer: Daniel Avraham
  • Location: Amado 719
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.
Print to PDF