The Taub Faculty of Computer Science Events and Talks

Recent years have seen a surge of activity in the field of arithmetic circuit lower bounds. Although there has been a tremendous improvement in our understanding of arithmetic circuits, they do not translate to analogues in the boolean world. In this talk, In this talk, we shall look at a possible approach towards strengthening arithmetic circuit lower bounds so that they may have relevance in the boolean world, namely via `functional' lower bounds.

We say that an arithmetic circuit C (over a field F) computes a polynomial P *functionally* if C(x) = P(x) on all of {0,1}^n. Importantly, C need not compute the same polynomial as P but as long as they agree on the boolean hyper-cube, we shall say C *functionally computes* P. In this talk we shall present a way to translate almost all recent lower bounds for shallow arithmetic circuits in to *functional lower bounds*. Although this does not yet give improve our understanding in the boolean world, it does take a step towards that goal.

This is part of a joint ongoing work with Michael Forbes and Mrinal Kumar.