research
∙
04/29/2020
On the Existence of Algebraically Natural Proofs
For every constant c > 0, we show that there is a family {P_N, c} of pol...
share
research
∙
11/28/2019
Schur Polynomials do not have small formulas if the Determinant doesn't!
Schur Polynomials are families of symmetric polynomials that have been c...
research
∙
04/30/2019
Derandomization from Algebraic Hardness: Treading the Borders
A hitting-set generator (HSG) is a polynomial map Gen:F^k →F^n such that...
research
∙
02/19/2019
Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
We show that any n-variate polynomial computable by a syntactically mult...
research
∙
07/17/2018
Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits
The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that an...
research
∙
04/24/2018
On Multilinear Forms: Bias, Correlation, and Tensor Rank
In this paper, we prove new relations between the bias of multilinear fo...
research
∙
08/07/2017
