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; such as social networks and google maps.

Here, the goal is to maintain a good solution to an optimization problem when the underlying input changes over time. This research area has seen exciting advances in the last decade.

In spite of this progress, however, we still have little understanding of how far, and extensively, can LP-based techniques be adapted to the world of dynamic algorithms. The proposal will bridge this chasm, by developing a dynamic algorithms centric theory of linear programming.

Further, it will show how to use this theory of dynamic LPs to push the frontier of fast static algorithms for fundamental graph problems.Building a launchpad out of some recent successes obtained by the PI, the proposal will attack outstanding open questions in both static and dynamic algorithms literature.

In addition, as a by-product of the versatility of its approach, it will have significant implications for algorithm design in other models of computation as well; such as online and sublinear algorithms.