We investigate the derandomized version of the classical line-point low-degree test in the high-error regime in the bivariate setting and reveal some unexpected behavior. The classical line-point low-degree test takes an $m$-variate function $f$ over a finite field $\mathbb{F}_q$, queries it along a random line and accepts if the restriction ... more >>>

In this paper we give polynomial-size hitting sets for multilinear any-order read-once oblivious algebraic branching programs and for depth-$3$ set-multilinear circuits where each variable set has constant size. Our results also extend to the border of both classes and hold over fields of any characteristic.

The proof combines the ... more >>>

We prove unconditionally that either NE contains a language requiring Boolean circuits of size at least $2^n/(2n)$, or $VP^0_{\mathbb{Z}}\ne VNP^0_{\mathbb{Z}}$, a constant-free version of Valiant's conjecture over the integers. The Boolean alternative implies that $NP\not\subseteq SIZE[n^k]$ for every constant $k\ge1$. Our proof gives a fine-grained variant of the connection between ... more >>>