research
∙
07/21/2022
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts
We say that two given polynomials f, g ∈ R[X], over a ring R, are equiva...
share
research
∙
07/20/2021
Functional lower bounds for restricted arithmetic circuits of depth four
Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there ex...
research
∙
03/12/2020
New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree
Kayal, Saha and Tavenas [Theory of Computing, 2018] showed that for all ...
research
∙
04/07/2018
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
We study the size blow-up that is necessary to convert an algebraic circ...
research
∙
10/16/2017