We introduce a new and very natural algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits ($VNP \neq VP$). As a ... more >>>

We describe obfuscation schemes for matrix-product branching programs that are purely algebraic and employ matrix algebra and tensor algebra over a finite field. In contrast to the obfuscation schemes of Garg et al (SICOM 2016) which were based on multilinear maps, these schemes do not use noisy encodings. We prove ... more >>>

We introduce a hitting set generator for Polynomial Identity Testing
based on evaluations of low-degree univariate rational functions at
abscissas associated with the variables. Despite the univariate
nature, we establish an equivalence up to rescaling with a generator
introduced by Shpilka and Volkovich, which has a similar structure but
uses ... more >>>