Circuits, communication and polynomials
Arkadev Chattopadhyay · eScholarship@McGill (McGill) · 2008
In this thesis, we prove unconditional lower bounds on resources needed to compute explicit functions in the following three models of computation: constant-depth boolean circuits, multivariate polynomials over commutative rings and the 'Number on the Forehead' model of multiparty communication. Apart from using tools from diverse areas, we exploit the rich interplay between these models to make progress on questions arising in the study of each of them.