All reports by Author Adrian She:

__
TR19-172
| 28th November 2019
__

Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan#### Schur Polynomials do not have small formulas if the Determinant doesn't!

__
TR19-170
| 27th November 2019
__

Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk#### A Quadratic Lower Bound for Algebraic Branching Programs

Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan

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 functions, in Representation theory [Sta99], in

Schubert calculus [LM10] as well as in Enumerative combinatorics [Gas96, Sta84,

Sta99]. In recent years, they have ...
more >>>

Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk

We show that any Algebraic Branching Program (ABP) computing the polynomial $\sum_{i = 1}^n x_i^n$ has at least $\Omega(n^2)$ vertices. This improves upon the lower bound of $\Omega(n\log n)$, which follows from the classical result of Baur and Strassen [Str73, BS83], and extends the results by Kumar [Kum19], which showed ... more >>>