A problem is downward self-reducible if it can be solved efficiently given an oracle that returns
solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is
well studied and it is known that all downward self-reducible problems are in PSPACE. In this
paper, we initiate the study of ... more >>>

We revisit the problem of constructing explicit pseudorandom generators
that fool with error $\epsilon$ degree-$d$ polynomials in $n$ variables
over the field $F_q$, in the case of large $q$. Previous constructions
either have seed length at least $2^{d}\log q$, and thus are only non-trivial
when the degree is less than ... more >>>

Let $\mathcal{F} = \{F_1, \ldots, F_m\}$ be a finite set of irreducible homogeneous multivariate polynomials of degree at most $3$ such that $F_i$ does not divide $F_j$ for $i\neq j$.
We say that $\mathcal{F}$ is a cubic radical Sylvester-Gallai configuration if for any two distinct $F_i,F_j$ there exists a ... more >>>