VP, VNP and Algebraic Branching Programs over Min Plus Semirings by Harshil Mittal

Value of the Information & Strength of the Argument

The value of this presentation lies in its detailed treatment of a subtle area of algebraic complexity. It clarifies how min-plus semiring computations exploit absorption to obtain resources not available in monotone arithmetic circuits. The speaker gives precise definitions of ‘‘produced polynomial’’, ‘’lower envelope’’, and the different semirings, ensuring that the lower-bound arguments are mathematically sound. The proof sketches are cohesive and explanatory, especially the adaptation of Brent’s depth reduction to R+ despite the absence of additive inverses. The discussion of width-2 and width-3 ABPs is well-structured, with concrete separations and constructions that illustrate the power of bounded-width computation. Open questions are implicitly raised, reinforcing the scientific value of the talk.

Scientific Rigor, Source Quality, Title Accuracy

The scientific rigor is high: the work builds on established results by Jukna, Brent, Ben-Or and Cleve, and the claims are supported by mathematical reasoning during the talk. The title exactly matches the content, since the lecture systematically addresses VP/VNP, algebraic branching programs, and min-plus semirings. The sole external source in the description is the ICTS program page, which may not contain full bibliographic references, but the formal nature of the presentation compensates for this. Overall, the focus is on rigorous derivation rather than informal speculation.

The title accurately reflects the content, as the talk defines min-plus semirings, discusses algebraic branching programs and explicitly relates them to VP/VNP and lower bounds.

8/10

Advanced research seminar at a recognized institution, presenting formal mathematical definitions, proofs, and new results. The argumentation is rigorous and builds on established prior work, although external citations are not fully listed in the description.

Markers derived by PSI from the transcript: the creator did not define chapters.

• 02:00Definition of semirings and introduction of the min-plus semiring, its operations and identity elements.
• 06:00Explanation of the absorption phenomenon in min-plus circuits and its role in separating min-plus from monotone arithmetic circuits.
• 09:00Application to shortest paths: walks absorb extra monomials and lead to the Bellman-Ford recurrence and associated skew circuits.
• 13:00Jukna's results: multilinear and homogeneous polynomials offer no extra min-plus power, yielding an exponential lower bound for the permanent.
• 18:00Introduction of algebraic branching programs, their width, and known results for low-width ABPs over fields.
• 24:00Width-2 ABPs are non-universal; impossibility for the polynomial sum x_i y_i and efficient computation of bivariate polynomials.
• 30:00Adaptation of Brent's depth reduction over R+ and construction of width-3 ABPs for sparse polynomials and bounded alternating formulas.

• ICTS Program: Circuits, Communication, and Proofs — Program page for the workshop where this lecture was given, providing context for the seminar series.