Towards a Dynamic Algorithms Centric Theory of Linear Programming

This proposal explores the interplay between two key concepts in theoretical computer science.(I) ""Linear programs"" (LPs) have historically played a pivotal role in the development of the field of algorithm design. The simple abstraction of an LP, which optimizes a linear function subject to a set of linear constraints, is powerful enough to encode a wide variety of combinatorial optimization problems. Accordingly, LP-based techniques are so ubiquitous today that any textbook on algorithms would be incomplete without a serious discussion on how to use them. (II) ""Dynamic algorithms"" have emerged as a popular model of computation in the 21st century, motivated by applications involving massive and rapidly evolving data-sets