Given a finite field $\mathbb F_q$, we say that a set $A\subseteq \mathbb F^n_q$ is an $(r,c)$ subspace evasive set if and only if for any affine subspace $U\subseteq \mathbb F^n_q$ with bounded dimension $\dim(U)\leq r$, the intersection size $|A\cap U|$ is at most $c$. The probabilistic method shows the ... more >>>

We establish a collection of new size lower bounds against fairly strong algebraic-Boolean propositional proof systems, from depth-3 semantic polynomial calculus for CNFs, up to semantic $AC^0[2]$-Frege in the regime of deep formulas, as follows:

(1) $\Sigma\Pi\Sigma$-PC: Exponential lower bound against semantic $\Sigma\Pi\Sigma$-PC over $F_2$, namely, polynomial calculus operating with ... more >>>

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