This is a follow-up to the previous question on the same topic. Thanks to Emil Jeřábek I can now ask a more specific question.
As before, let $k$ be a field with $p$ elements. Consider the following computational problem.
Input: a natural number $n$, $n^2$ linear forms $M_{ij}$, $i,j=1,\ldots n$ in $n^2$ variables $X_{11}, \ldots X_{nn}$.
Problem: Is there an assignment of values to the variables $X_{ij}$ so that the matrix $M_{ij}$ is invertible?
As usually, let's assume the addition and multiplication in the field to have computational cost $1$.
On the one hand, we have a trivial algorithm of checking all the possible assignments for $X_{ij}$, and for each such assignment checking by Gauss elimination whether the resulting matrix is invertible. This takes time bounded by a polynomial in $p^{n^2}$.
On the other hand, Emil Jeřábek showed previously that we can encode a 3-SAT instance consisting of $n$ clauses into a $3n\times 3n$ matrix of linear forms which is invertibe iff the 3-SAT instance is satisfiable. Assuming exponential time hypothesis this gives a lower bound on the problem above of the form $O(2^{\delta n})$ for some $\delta>0$.
Question 1 Is there an algorithm for the problem above, whose execution time is bounded by a polynomial in $p^{n^\alpha}$ for $\alpha <2$?
Question 2 Is there a natural number $k$ such that one can encode a 3-SAT instance with $n^\beta$ clauses into a problem as above for a $kn\times kn$ matrix, for $\beta>1$?
