The project proposes to study three related areas of computational complexity: circuit and branching program lower bounds, multi-party communication complexity and derandomization. In the first area we propose to study the size of bounded-depth counting circuits and the depth of Boolean circuits needed to compute explicit functions. Furthermore, we propose to study the recently introduced variants of branching programs---incremental and tight branching programs. In the area of multiparty communication complexity we want to focus on the relationship among deterministic, nondeterministic and randomized protocols. In the area of derandomization we want to consider several key problems related to derandomization of space-bounded computation.
Main investigator:
Site map | Author | Webmaster
