2 papers
cs.CC2019
Schur Polynomials do not have small formulas if the Determinant doesn't!
Prasad Chaugule, Mrinal Kumar, Nutan Limaye +3
Schur Polynomials are families of symmetric polynomials that have been classically studied in Combinatorics and Algebra alike. They play a central role in the study of Symmetric fu…
cs.CC2019
A Quadratic Lower Bound for Algebraic Branching Programs and Formulas
Prerona Chatterjee, Mrinal Kumar, Adrian She +1
We show that any Algebraic Branching Program (ABP) computing the polynomial has at least vertices. This improves upon the lower bound of $Ω(n\log n)…