A Polyhedral Perspective on Tropical Convolutions

Abstract

Tropical (or min-plus) convolution is a well-studied algorithmic primitive in fine-grained complexity. We exhibit a novel connection between polyhedral formulations and tropical convolution, through which we arrive at a dual variant of tropical convolution. We show this dual operation to be equivalent to primal convolutions. This leads us to considering the geometric objects that arise from dual tropical convolution as a new approach to algorithms and lower bounds for tropical convolutions. In particular, we initiate the study of their extended formulations.