The Graph Isomorphism problem can be reduced to the Gowers hybrid problem.
Given a pair $A,B$ of graphs, each with $n$ vertices, we seek to construct a graph $G_{A,B}$ whose Hamiltonicity is equivalent to $A$ and $B$ being isomorphic. Moreover, we shall construct this carefully as to not break any symmetry: if $A,A'$ are isomorphic, and $B,B'$ are isomorphic, then so are $G_{A,B}$ and $G_{A',B'}$.
Now, given a graph isomorphism problem determined by graphs $A,B$, we consider the Gowers hybrid problem with graphs $G_{A,A}$ and $G_{A,B}$. By construction, these are isomorphic if $A, B$ are isomorphic. Otherwise, $G_{A,A}$ is Hamiltonian and $G_{A,B}$ is not.
Provided we can perform such a construction in polynomial time, and ensure that the order of $G_{A,B}$ is polynomial in $n$, then Graph Isomorphism and the Gowers hybrid problem are equally difficult (i.e. there is a polynomial-time reduction between them).
The rest of this answer is simply describing this construction.
Let $A,B$ be a pair of graphs on the vertex-set $[n] := \{ 1, 2, \dots, n \}$.
We create a variable $v_{a,b}$ for every ordered pair $(a,b)$ of a vertex in $A$ and a vertex in $B$. Then, we write down the clauses:
- $(\neg v_{a_i,b_j} \lor \neg v_{a_i,b_k}) \forall i,j,k \in [n]$
- $(\neg v_{a_j,b_i} \lor \neg v_{a_k,b_i}) \forall i,j,k \in [n]$
- $(v_{a_i,b_1} \lor v_{a_i,b_2} \lor \cdots \lor v_{a_i,b_n}) \forall i \in [n]$
- $(v_{a_1,b_i} \lor v_{a_2,b_i} \lor \cdots \lor v_{a_n,b_i}) \forall i \in [n]$
which specify that our variables describe a bijection between the vertex-sets of $A$ and $B$. Then, for every edge $(a,a')$ and non-edge $(b,b')$, we specify the clause:
- $(\neg v_{a,b} \lor \neg v_{a',b'})$
and do the same for non-edges in $A$ and edges in $B$. This forces our variables to specify an isomorphism between the graphs $A$ and $B$.
Now, the following page reduces $3$-SAT to vertex cover:
http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2001/CW/npproof.html
We need $k$-SAT rather than $3$-SAT, but we can note that the triangle-shaped gadget described on this page can be replaced with an arbitrary-sized complete graph $K_k$ to allow clauses of arbitrary length: we can cover the edges within the complete graph with $k-1$ vertices (and no fewer) provided at least one of the adjoining $k$ edges is already covered.
So far, we have constructed a vertex-covering problem of a graph which (up to isomorphism) only depends on the graphs $A, B$ up to isomorphism. Moreover, it has a vertex cover of the correct size if and only if $A$ and $B$ are isomorphic.
Now appeal to this result:
http://web.math.ucsb.edu/~padraic/ucsb_2014_15/ccs_problem_solving_w2015/Hamiltonian%20Circuits.pdf
which shows how to convert a vertex-covering problem into a Hamiltonian cycle problem, again canonically (so not depending on how we've labelled the vertices of our graphs).
Hence, we can canonically construct a graph $G_{A,B}$ which has a Hamiltonian cycle if and only if $A$ and $B$ are isomorphic. Moreover, $G_{A,B}$ up to isomorphism only depends on $A, B$ up to isomorphism. Also, $G_{A,B}$ is only of size polynomial in $n$ (namely $O(n^4)$ vertices if I counted correctly).
The result follows.