13 citations · 53 across the 21 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.CC2015★ 5 cited
Sums of products of polynomials in few variables : lower bounds and polynomial identity testing
Mrinal Kumar, Shubhangi Saraf
We study the complexity of representing polynomials as a sum of products of polynomials in few variables. More precisely, we study representations of the form $$P = \sum_{i = 1}^T…
cs.CC2015
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Swastik Kopparty, Or Meir, Noga Ron-Zewi +1
In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query co…