What is the current time limit of Keccak inversion?
But for this reason I would argue it’s the most valuable sub-function to study if we are to determine the theoretical time limit of Keccak inversion.


That is incorrect as you don't need a time limit to compute $\theta^{-1}$.

You are not using the correct representation. As follows are some intuitions of how to efficiently invert $\theta$.

I. Quick Reminder of $\theta$



II. Inverting the $\theta$-effect

Instead of seeing the parity  $\mathscr{P}$ of the state $S$ as $5 \times w$ bit-array. You can see it as  a $5w$-bit vector $W$. i.e. you have a unique mapping $\sigma$  between $x,z$ and $i^{th}$ the coordinate in that $5w$-bit vector $W$ : $i = x \times w + z$.
$$\varphi(\mathscr{P}) = W$$

The $\theta$-effect can be seen as the result of a matrix multiplication:
$$W' = W \cdot T$$
which gives us:
$$E = \varphi^{-1}\circ (\lambda x \mapsto x\cdot T) \circ \varphi$$
and the inverse: 
$$E^{-1} = \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ \varphi$$
Note: this assumes that $T^{-1}$ exists.

Proof:
\begin{array}{rl}
E^{-1} \circ E &amp;= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ \varphi \circ \varphi^{-1}\circ (\lambda x \mapsto x\cdot T) \circ \varphi\\
 &amp;= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ  (\lambda x \mapsto x\cdot T) \circ \varphi\\
 &amp;= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T \cdot T^{-1}) \circ \varphi\\
 &amp;= \varphi^{-1}\circ (\lambda x \mapsto x) \circ \varphi\\
 &amp;= \varphi^{-1}\circ \varphi\\
 &amp;= id
\end{array}

As an example as follow is computed $T$ for $w = 4$:

i =  0 : 0 0 0 0   1 0 0 0   0 0 0 0   0 0 0 0   0 0 0 1
i =  1 : 0 0 0 0   0 1 0 0   0 0 0 0   0 0 0 0   1 0 0 0
i =  2 : 0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 0   0 1 0 0
i =  3 : 0 0 0 0   0 0 0 1   0 0 0 0   0 0 0 0   0 0 1 0

i =  4 : 0 0 0 1   0 0 0 0   1 0 0 0   0 0 0 0   0 0 0 0
i =  5 : 1 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0   0 0 0 0
i =  6 : 0 1 0 0   0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 0
i =  7 : 0 0 1 0   0 0 0 0   0 0 0 1   0 0 0 0   0 0 0 0

i =  8 : 0 0 0 0   0 0 0 1   0 0 0 0   1 0 0 0   0 0 0 0
i =  9 : 0 0 0 0   1 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0
i = 10 : 0 0 0 0   0 1 0 0   0 0 0 0   0 0 1 0   0 0 0 0
i = 11 : 0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 1   0 0 0 0

i = 12 : 0 0 0 0   0 0 0 0   0 0 0 1   0 0 0 0   1 0 0 0
i = 13 : 0 0 0 0   0 0 0 0   1 0 0 0   0 0 0 0   0 1 0 0
i = 14 : 0 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0   0 0 1 0
i = 15 : 0 0 0 0   0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 1

i = 16 : 1 0 0 0   0 0 0 0   0 0 0 0   0 0 0 1   0 0 0 0
i = 17 : 0 1 0 0   0 0 0 0   0 0 0 0   1 0 0 0   0 0 0 0
i = 18 : 0 0 1 0   0 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0
i = 19 : 0 0 0 1   0 0 0 0   0 0 0 0   0 0 1 0   0 0 0 0


If we take point at coordinates $(x = 0, z = 3)$ or $i = 0\times 4 + 3 = 3$ (thus the fourth column).

The $\theta$-effect gives us:

$(x-1, z) + (x+1,z+1) = (4,3) + (1,0)$ as we are with $w = 4$.

In other words we need:

$i = 4 \times 4 + 3 = 19$ and $i = 1 \times 4 + 0 = 4$.

You can check that these coordinates are set in the $4^{th}$ column.

Fun fact, $T$ is not invertible.

For $T$ to be invertible, the determinant should not be null. Using sage we notice that $det(T) = 0$, proving that $T$ is not invertible.

III. Going back to $\theta$

Sadly inverting the (non-invertible) $\theta$-effect does not gives us the inverse of $\theta$ as it is added back to the state. However we can notice multiple things.

   +---+       +---+
  /   /|      /   /|
 /   / +     /   / +
+---+ /     +---+ /
| S |/ ---&gt; | S'|/
+---+       +---+
  |           ^
  v           |
  P  ------&gt; E(P)


Notice that:


$\bigoplus_{y=0}^4 S[x,y,z] = \mathscr{P}$
$\bigoplus_{y=0}^4 S'[x,y,z] = \mathscr{P} + 5 \times E(\mathscr{P}) = P + E(\mathscr{P})$


In the same way as in [II], $P + E(\mathscr{P})$ can be seen as a matrix transformation (i.e. a multiplication by $(id + T)$).

Thus if we inverse this $(id + T)$ matrix, we will be able to find the initial parity $\mathscr{P}$ of the state, compute the $\theta$-effect and add it back to $S'$, canceling the itself ($\forall s, s \oplus \theta\text{-effect} \oplus \theta\text {-effect} = s$). And in such way, computing the inverse of $\theta$.

   +---+                              +---+
  /   /|                             /   /|
 /   / +                            /   / +
+---+ /        theta^-1            +---+ /
| S'|/ --------------------------&gt; | S |/
+---+                              +---+
  |                                  ^
  v                                  |
P + E(P) ---------------&gt; P ----- &gt; E(P)
          *(id + T)^-1        *T


Going back to our $w= 4$ example we have:

id + T =
[1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
[0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0]
[0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1]
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1]


Which happens to be invertible:

(id+T)^-1=
[1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0]
[0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1]
[1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1]
[1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0]
[0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1]
[0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1]
[1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0]
[1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1]
[1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1]
[1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1]
[0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0]
[0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0]
[1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0]
[1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0]
[1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0]
[0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0]
[0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1]
[0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1]
[0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1]


Because of the associativity of the matrix group. You can just compute: $(id + T)^{-1} \cdot T$ giving you a slightly faster computation of the $\theta$-effect from $S'$ (as opposed to do the 2 matrix multiplications):

(id + T)^-1 * T =
[0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0]
[0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1]
[1 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1]
[1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0]
[0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1]
[0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1]
[1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0]
[1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1]
[1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1]
[1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1]
[0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0]
[0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0]
[1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0]
[1 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0]
[1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0]
[0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0]
[0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1]
[0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1]
[0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0]