research
∙
08/08/2023
Determinants vs. Algebraic Branching Programs
We show that for every homogeneous polynomial of degree d, if it has det...
share
research
∙
11/26/2022
Extractors for Images of Varieties
We construct explicit deterministic extractors for polynomial images of ...
research
∙
09/09/2022
Tensor Reconstruction Beyond Constant Rank
We give reconstruction algorithms for subclasses of depth-3 arithmetic c...
research
∙
06/06/2021
Lower Bounds on Stabilizer Rank
The stabilizer rank of a quantum state ψ is the minimal r such that | ψ⟩...
research
∙
09/05/2020
A Lower Bound on Determinantal Complexity
The determinantal complexity of a polynomial P ∈𝔽[x_1, …, x_n] over a fi...
research
∙
03/29/2020
A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits
We show that there is a defining equation of degree at most 𝗉𝗈𝗅𝗒(n) for ...
research
∙
11/26/2019
A Quadratic Lower Bound for Algebraic Branching Programs and Formulas
We show that any Algebraic Branching Program (ABP) computing the polynom...
research
∙
11/26/2019
A Quadratic Lower Bound for Algebraic Branching Programs
We show that any Algebraic Branching Program (ABP) computing the polynom...
research
∙
04/02/2019
Lower Bounds for Matrix Factorization
We study the problem of constructing explicit families of matrices which...
research
∙
08/07/2017
Pseudorandom Bits for Oblivious Branching Programs
We construct a pseudorandom generator which fools read-k oblivious branc...
research
∙
08/07/2017