| Title | : | VP, VNP and Algebraic Branching Programs over Min-plus Semirings |
| Speaker | : | Harshil Mittal (IIT Madras) |
| Details | : | Mon, Jun 29, 2026 11:30 AM, @ SSB 334 (Turing Hall) |
| Abstract | : | Pure dynamic programming algorithms are DPs whose recurrences use only min and + operations (e.g., Bellman-Ford algorithm for Shortest s-t path problem); these can be viewed as circuits consisting of min and + gates. Typically, algebraic circuits consist of + and × gates, where + and × are addition & multiplication operations of some field, respectively; (min, +)-circuits are similar except that one works over a min-plus semiring (instead of a field), i.e., where addition and multiplication of the semiring are defined as minimum operation and usual addition, respectively. Over fields, algebraic models such as circuits, formulas, and algebraic branching programs (ABPs) are well studied. In this talk, we will discuss these models over min-plus semirings (motivated by an understanding of the power/limitations of pure DPs) and some of the known results. We define VNP over min-plus semirings. Unlike over rings, we complement the values in the certificate for free, as complementation is impossible over min-plus semirings. We prove a dichotomy theorem that states that if we only complement logarithmically many values, this class is the same as VP over min-plus semirings. If we complement super-logarithmically many values, then VNP is different from VP. We consider constant-width ABPs over the min-plus semiring (which are also called incremental dynamic programs that are restricted to use only a constant number of registers) and show that even simple problems like computing the min-weight 2-edge-matching is impossible with width 2 (or 2 registers). However, with width 3 (or 3 registers), such programs are universal. More generally, we show that constant-depth formulas are efficiently simulated by constant-width ABPs. (Based on a joint work with Balagopal Komarath and Jayalal Sarma, to appear at ICALP 2026) |