Lower bounds for read-once and tropical formulas[HBNI Th143]

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.