Complexity of unbalanced bipartite isomorphism For $i=1,2$, let $G_i=(A_i\cup B_i,E_i)$ be an undirected bipartite 
graph with bipartition $A_i$ and $B_i$, where $|A_1|=|A_2|=a$ and 
$|B_1|=|B_2|=b$ with $a\le b$.


  Question. Is the problem of deciding isomorphism between 
  such graphs solvable in $O(b^k 2^a)$ time, for some constant $k&gt;0$?


Note that Babai's result yields a $2^{(\log(a+b))^c}$ time 
algorithm for some constant $c&gt;1$. 
For the cases with $a=O(\log b)$, a solution to my question would
yield a polynomial time complexity.
If you are willing to relax the 2 to some other constant, then yes: this can be solved in $O(c^a)$ time for some absolute constant $c$. You can view this problem as isomorphism of hypergraphs, where the vertices in $A_i$ are the vertices of your hypergraph, and the vertices in $B_i$ are hyperedges. Luks (STOC '99) showed how to solve hypergraph isomorphism for hypregraphs on $a$ vertices in $O(c^a)$ time for some absolute constant $c$.