We got a reduction graph isomorphism to MIS in a very dense graph, or alternatively negative monotone 2-CNF to MAX-ONEs with a formula with many clauses.
Let $G,H$ be graphs of order $n$ and adjacency matrices $A_1,A_2$ and consider the reduction graph isomorphism to MAX-ONEs CNF $J$.
If $G$ and $H$ are isomorphic iff there exist permutation matrix $P$ such that $A_2=P A_1 P^{-1}=P A_1 P^T$.
Let $P$ by $n$ by $n$ matrix with entries 0/1 variables $x_1,...x_n^2$.
For each row and for each column of $P$ add to $J$ the CNF clauses $(-x_i,-x_j)$, that is at most one variable per row or column is $1$.
So far we don't add the constraints at least variable to be $1$ because MAX-ONEs (alternatively MIS) will take care of this.
Let $B=P A P^T$. The entries of $B$ are quadratic polynomials with positive coefficients.
For $1\le i,j,\le n$, let $q=B[i,j]$ iff $A_2[i,j]=0$ (otherwise do nothing). For each monomial $m=c_i x_i x_j$ of $q$ add the constraint $(-x_i,-x_j)$ since if both variables are $1$ the entry in $A_2[i,j]$ will be nonzero.
We claim that $J$ has solutions with $n$ ones iff $G$ and $H$ are isomorphic since the ones will make $P$ permutation matrix and $B=A_2=P A_1 P^T$
Alternatively, make $G'$ graph with edges the clauses of $J$. it is of order $n^2$ and edges $n^C$ for $C \ge 3$.
$G'$ has independent set of size $n$ iff $G,H$ are isomorphic.
The clauses of $J$ are also at least $n^3$.
Define the logarithmic density of graph $glog(G)=\frac{\log(|E(G)|}{\log(|V(G|)|}$.
We believe very dense graphs might have easier complexity of IS, since complements of bounded degree graphs have few independent sets and adding large degree vertex to the IS deletes all neighbors, reducing the size.
What is the complexity of finding $n$-independent set in $G'$, possibly for some restricted graph classes?
We have experimental support and in our sagemath implementation, the running time was dominated by computing the matrix product.
