Ben lee Volk

activity

20172026

most citedRecursive Error Reduction for Regular Branching Programs

1 citations · 1 across the 7 of their papers we have counts for

collaborators

Showing 2019Show all

2 papers · 1 filter

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 $\sum_{i = 1}^{n} x_{i}^{n}$ has at least $Ω (n^{2})$ vertices. This improves upon the lower bound of $Ω(n\log n)…

cs.CC2019

Lower Bounds for Matrix Factorization

Mrinal Kumar, Ben Lee Volk

We study the problem of constructing explicit families of matrices which cannot be expressed as a product of a few sparse matrices. In addition to being a natural mathematical ques…