Abstract:
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.
An arithmetic read-once formula (ROF) is a formula (circuit of fan-out 1) over
+, ⇥ where each variable labels at most one leaf. Every multilinear polynomial can
be expressed as the sum of ROFs. We prove, for certain multilinear polynomials, a
tight lower bound on the number of summands in such an expression.
We then proceed to study computation by tropical formulas or formulas over
(min, +). Many dynamic programming algorithms can be modeled using (min, +)
formulas. We consider the computation of max(x1, x2,...,xn) over N as a di↵erence
of (min, +) formulas, and show that size n + n log n is sucient and necessary. Our
proof also shows that any (min, +) formula computing the minimum of all sums of
n 1 out of n variables must have n log n leaves; this too is tight. Our proofs use a
complexity measure for (min, +) functions based on minterm-like behaviour and on
the entropy of an associated graph.
Next, we consider the well-studied shortest paths problem shortest-path:
Given a graph on vertex set [n] = {1, 2,...,n} with an assignment of non-negative integer weights to its edges, we want to find a (min, +) formula which computes
the weight of the shortest path from s = 1 to t = n. We study bounded-depth
(min, +) formulas solving the shortest paths problem. For depth 2d with d 2, we
obtain lower bounds parameterized by certain fan-in restrictions on + gates except
those at the bottom level. For the special case of depth four, in two regimes of the
parameter, the bounds are tight.
