Joshua Grochow, Toniann Pitassi

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 >>>

Craig Gentry, Charanjit Jutla

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 >>>

Dieter van Melkebeek, Andrew Morgan

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 >>>