Alladi Ramakrishnan Hall

(PhD Thesis Defense) 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.