Room 327

Lower bounds for read-once and tropical formulas

Anuj Tawari

IMSc, HBNI

One of the major aims of theoretical computer science is to understand what is the most efficient way to perform a given task with limited computational resources. In this thesis, some absolutely tight lower bounds are shown for certain restricted models of computation. More specifically, this thesis studies the questions of proving tight lower bounds for sums of read-once formulas, and of proving tight lower bounds for tropical formulas.