2 papers
cs.CC2022
Degree-restricted strength decompositions and algebraic branching programs
Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer +1
We analyze Kumar's recent quadratic algebraic branching program size lower bound proof method (CCC 2017) for the power sum polynomial. We present a refinement of this method that g…
cs.CC2020
Limitations of Sums of Bounded-Read Formulas
Purnata Ghosal, B. V. Raghavendra Rao
Proving super polynomial size lower bounds for various classes of arithmetic circuits computing explicit polynomials is a very important and challenging task in algebraic complexit…