$\DeclareMathOperator\Rep{Rep}\DeclareMathOperator\Vect{Vect}\DeclareMathOperator\Aut{Aut}\DeclareMathOperator\Mod{Mod}\DeclareMathOperator\GL{GL}\DeclareMathOperator\Hom{Hom}$The infinitude of the input data is deceptive. For example, an infinite finitely presented group may appear to be infinite input data but it's fully specified by a finite alphabet and a finite set of words in it. The same sort of thing happens here; everything is "finitely presented" in a suitable sense.
First, let's recall the statement of Tannaka-Krein duality here so we can see exactly how the group arises. Let $G$ be a finite group and let $\Rep(G)$ be its category of representations (say over $\mathbb{C}$). $\Rep(G)$ is equipped with a monoidal structure in the form of the tensor product of representations and with a forgetful functor $F : \Rep(G) \to \Vect$. We are interested in studying natural automorphisms $\eta : F \to F$ compatible with the tensor product in the sense that the obvious diagram (which can be found on page 8 of Commelin - Tannaka duality for finite groups for completeness) commutes. Every element of $G$ gives an element of this group of natural automorphisms, which we'll denote $\Aut^{\otimes}(F)$.
Theorem: The natural map $G \to \Aut^{\otimes}(F)$ is an isomorphism.
So our reconstruction begins first with the group $\Aut(F)$ of natural automorphisms of $F$, then cuts out a subgroup satisfying some extra compatibility conditions. Let's start with figuring out what data we need to describe $\Aut(F)$.
Explicitly, an element of $\Aut(F)$ is a family $\eta_V : F(V) \to F(V)$ of automorphisms of the underlying vector spaces of all representations of $G$ which is compatible with all morphisms between representations. There is a universal such representation generated by a single element, namely $\mathbb{C}[G]$ regarded as a representation via left multiplication, and compatibility with all morphisms $\mathbb{C}[G] \to V$ implies that any such natural transformation $\eta$ is completely determined by what it does to $\mathbb{C}[G]$. On $\mathbb{C}[G]$ any such natural transformation needs to be compatible with right multiplication, and so must be left multiplication by some invertible element of $\mathbb{C}[G]$. Conversely any such element gives an element of $\Aut(F)$. Hence
$$\Aut(F) \cong \mathbb{C}[G]^{\times} \cong \prod_i \GL(V_i)$$
where the $V_i$ are the irreducible representations of $G$. (Secretly we are using the Yoneda lemma but I wanted to be completely explicit.) This reflects the fact that the data of the category and the fiber functor is equivalent to the data of the number and dimensions of the irreducible representations respectively. So we can use these as our initial data:
Data 1, 2: The number $n$ of irreducible representations and their dimensions $d_i$.
This step of the reconstruction reflects a more general fact, namely that if $R$ is a $k$-algebra, $\Mod(R)$ the category of left $R$-modules, and $F : \Mod(R) \to \Vect$ the forgetful functor, then the natural endomorphisms of $F$ are canonically isomorphic to $R$ (as a $k$-algebra), which again follows from the Yoneda lemma.
The tricky part is how to describe the influence of the tensor product. Explicitly, let $\eta : F \to F$ be an element of $\Aut(F)$ again. Then there are two ways to use $\eta$ to write down an automorphism of the underlying vector space of a tensor product $F(V \otimes W)$:
- On the one hand, there are two maps $\eta_V : F(V) \to F(V)$ and $\eta_W : F(W) \to F(W)$, and we can tensor them to get a map $\eta_V \otimes \eta_W : F(V) \otimes F(W) \to F(V) \otimes F(W)$. Since $F$ is a tensor functor this gives a map $F(V \otimes W) \to F(V \otimes W)$.
- On the other hand, there is a map $\eta_{V \otimes W} : F(V \otimes W) \to F(V \otimes W)$.
$\eta$ lies in $\Aut^{\otimes}(F)$ if and only if these are equal. More explicitly, if $\eta$ is left multiplication by some element $\sum c_g g \in \mathbb{C}[G]$, then the first map is
$$\left( \sum c_g \rho_V(g) \right) \otimes \left( \sum c_g \rho_W(g) \right)$$
while the second map is
$$\sum c_g \rho_V(g) \otimes \rho_W(g)$$
and setting $V = W = \mathbb{C}[G]$ and comparing coefficients shows that these can't be equal unless $\sum c_g g = g$ for some $g$.
So how do we describe this restriction to a computer? The key point is that since everything in sight is compatible with direct sums it suffices to restrict our attention to the irreducible representations $V_i$, so we only need to compare the maps $\eta_{V_i} \otimes \eta_{V_j}$ and $\eta_{V_i \otimes V_j}$ for all $i, j$. This means that we need to describe
- How two maps $F(V_i) \to F(V_i), F(V_j) \to F(V_j)$ tensor to give a map $F(V_i \otimes V_j) \to F(V_i \otimes V_j)$ for all $i, j$, and
- How knowing $\eta_{V_i}$ for all $i$ determines $\eta_{V_i \otimes V_j}$ for all $i, j$.
This requires that we know first of all the decompositions
$$V_i \otimes V_j \cong \bigoplus_k m_{ijk} V_k$$
of the tensor products of the irreducibles into irreducibles. So this is our third piece of data:
Data 3: The multiplicities $m_{ijk}$.
These multiplicities are equivalent to the data of the character table of $G$, and in particular it is possible to compute Data 1, 2 from this data, so in some sense Data 1, 2 are redundant. But we already know that the character table is not enough. The multiplicities only tell us about $\eta_{V_i \otimes V_j}$, but not about $\eta_{V_i} \otimes \eta_{V_j}$.
To get our last piece of data, let's think about how a computer would represent $\eta$. Specifying linear transformations $\eta_{V_i} \in \GL(V_i)$ requires writing down a basis of each $V_i$. These bases give rise to two different bases of the tensor products $V_i \otimes V_j$: on the one hand the tensor product basis, and on the other hand the basis coming from the decomposition into irreducibles $\bigoplus_k m_{ijk} V_k$. So the final piece of data we need is the identification between these:
Data 4: For every pair $i, j$, the $(d_i \times d_j)$ by $(d_i \times d_j)$ transition matrix from the tensor product basis to the decomposition basis of $V_i \otimes V_j$.
(This is essentially the data of the identifications $F(V \otimes W) \cong F(V) \otimes F(W)$ making $F$ a tensor functor: unlike in the case of maps between monoids, being a tensor functor is a structure, not a property, because these maps are required to satisfy coherence conditions.)
This is the data we need to write $\eta_{V_i} \otimes \eta_{V_j}$ and $\eta_{V_i \otimes V_j}$ as matrices with respect to the same basis. These transition matrices should be definable over a splitting field of $G$ at worst, so this really is finite data.
Edit, 12/26/21: Wow, sorry everyone, there's actually a small gap here that needs to be fixed. The "decomposition basis" I described above is not well-defined because the decomposition of $V_i \otimes V_j$ into irreducibles isn't unique when the multiplicities are greater than $1$! Instead we need to proceed as follows: the truly fully canonical decomposition into irreducibles takes the form
$$V_i \otimes V_j \cong \bigoplus_k \text{Hom}_G(V_k, V_i \otimes V_j) \otimes V_k$$
where the tensor product on the RHS is just the ordinary tensor product of vector spaces. To get a decomposition basis as claimed above we need to make additional choices, namely a choice of basis for each homspace $\Hom_G(V_k, V_i \otimes V_j)$. I don't think this choice really ends up mattering but I think it does still need to be made? Maybe a slightly nicer approach could avoid it.
