This problem was simplified by Alex Ravsky (thanks!). For the original problem see below.
Simplified Problem
With $f(k_1,k_2,\ldots,k_n)$ a polynomial over $GF(2)$, find the value of the coefficient of the term that contains all variables $k_i$ (in other words the coefficient $a\in GF(2)$ of the term $a\prod_{i=1}^n k_i$). There is only one such term in the simplified polynomial because $\forall x\in GF(2),n\in \mathbb{N}: x^n=x$. However, $f$ is too long to be multiplied out completely in practice and can only be represented as a tree of nested sums and products (in which most leaves are present at multiple points throughout the tree). Even though this simpler than the original problem, finding that coefficient algorithmically in polynomial time is still proving challenging and I would appreciate all the help I can get! :D
Original Problem
Essentially I have a nested sum in the form $$\sum_{k_1=0}^1 \sum_{k_2=0}^1 \ldots \sum_{k_n=0}^1 f(k_1,k_2,\ldots,k_n)$$ where $f(k_1,k_2,\ldots,k_n)$ is a multivariate polynomial over $GF(2)$ which can only be represented as a tree of nested sums and products because multiplying it out would lead to on average $2^{n-1}$ terms (the number of possible terms is $2^n$ because in $GF(2)$ every $k_i=k_i^j$ for $j\in\mathbb{N}$ and the number of possible variable combinations $1;k_1;k_2;k_2k_1;k_3;k_3k_1;k_3k_2;k_3k_2k_1;\ldots$ is $2^n$).
Finding the value of $f$ for a specific set of $k_i$ is trivial, but the exponential time complexity of doing this $2^n$ times (the total number of elements in our nested sum) is a bit of a buzzkill. I'm a patient guy but not enough so to wait longer than the age of the universe, so I'd much prefer to do this in polynomial time :)
So far, I've tried reordering the sum to $$\sum_{k_1=0}^1 \ldots \sum_{k_{i-1}=0}^1 \sum_{k_{i+1}=0}^1 \ldots \sum_{k_n=0}^1 \sum_{k_i=0}^1 f(k_1,k_2,\ldots,k_n)$$ for some specific $i$ and finding $a,b \in GF(2)$ such that $f(k_1,k_2,\ldots,k_n)=k_ia+b$ (where $a$ and $b$ are each polynomials independent of $k_i$ represented as a tree similar to $f$; this is trivial to do for a single $k_i$) because in $GF(2)$ I can then do $$\sum_{k_i=0}^1 f(k_1,k_2,\ldots,k_n)=\sum_{k_i=0}^1 (k_ia+b)=0a+b+1a+b=a+b+b=a$$ which means that $$\sum_{k_1=0}^1 \sum_{k_2=0}^1 \ldots \sum_{k_n=0}^1 f(k_1,k_2,\ldots,k_n)=\sum_{k_1=0}^1 \ldots \sum_{k_{i-1}=0}^1 \sum_{k_{i+1}=0}^1 \ldots \sum_{k_n=0}^1 a$$ which in turn means that I've halved the number of elements of the nested sum. However, the complexity of $a$ is usually higher than the complexity of $f$, because when isolating $k_i$ from $f$, the following happens each time a product is encountered in the tree representing $f$, of which at least two factors are dependent on $k_i$:
Let $k_ia_1+b_1$ and $k_ia_2+b_2$ be two such factors from which $k_i$ is to be isolated such that we obtain an $a_0$ and $b_0$ with $k_ia_0+b_0=(k_ia_1+b_1)(k_ia_2+b_2)$. Finding $$(k_ia_1+b_1)(k_ia_2+b_2)=k_i^2a_1a_2+k_ia_1b_2+k_ia_2b_1+b_1b_2=k_ia_1a_2+k_ia_1b_2+k_ia_2b_1+b_1b_2=k_i(a_1a_2+a_1b_2+a_2b_1)+b_1b_2$$ is simple, however, even if this were the closest such product to the base of the tree, which would mean that $b_0$ falls away due to the mechanism described above, and even if I rewrite $a_0=a_1a_2+a_1b_2+a_2b_1=(a_1+b_1)(a_2+b_2)+b_1b_2$ to minimize the number of products added to the tree, I've just added at least two products to the tree, each of which will add at least two more products to the tree when I isolate the next $k_j$ because $a_1,a_2,b_1,$ and $b_2$ are almost certain to be dependent on $k_j$. Therefore, we're back to the exponential time complexity. Unfortunately, I have not been able to find a way to get around this problem.
Because we're in $GF(2)$, of course, this problem stays identical if all of the equalities above are replaced with congruences modulo $2$ in $\mathbb{Z}$. I don't actually know if it's easier to think of the problem in such terms, however.
Thank you so much for making it this far through my lengthy question! I very much look forward to reading your ideas :)
Given $f$, put $S(f)=\sum_{k_1=0}^1 \sum_{k_2=0}^1 \ldots \sum_{k_n=0}^1 f(k_1,k_2,\ldots,k_n)$. As I understood, the complexity of an algorithm calculating $S(f)$ depends on the representation of $f$. Indeed, put $\Bbb F=GF(2)$ and $[n]=\{1,\dots,n\}$. Since $x^j=x$ for each $x\in\Bbb F$ and $j\in\mathbb{N}$, there exists a polynomial $\bar f\in\Bbb F[x_1,\dots,x_n]$ such that $\bar f(x_1,\dots,x_n)=f(x_1,\dots,x_n)$ for each $x_1,\dots,x_n\in\Bbb F$ and $\bar f$ has degree at most $1$ with respect to each variable. Then $\bar f(x_1,\dots,x_n)=\sum_{A\subset [n]} a_A\prod_{i\in A} x_i$, where $a_A$’s belong to $\Bbb F$ and, for the convenience, $\prod_{i\in \varnothing} x_i=1$. Remark that $\prod_{i\in A} k_i$ equals $1$, if $k_i=1$ for each $i\in A$, and equals $0$, otherwise. Then $$S(f)=\sum_{k_1=0}^1 \sum_{k_2=0}^1 \ldots \sum_{k_n=0}^1 f(k_1,k_2,\ldots,k_n)=$$ $$\sum_{k_1=0}^1 \sum_{k_2=0}^1 \ldots \sum_{k_n=0}^1 \bar f(k_1,k_2,\ldots,k_n)=$$ $$\sum_{k_1=0}^1 \sum_{k_2=0}^1 \ldots \sum_{k_n=0}^1 \sum_{A\subset [n]} a_A\prod_{i\in A} k_i=$$ $$\sum_{A\subset [n]} \sum_{k_1=0}^1 \sum_{k_2=0}^1 \ldots \sum_{k_n=0}^1 a_A\prod_{i\in A} k_i=$$ $$\sum_{A\subset [n]}2^{n-|A|} a_A= a_{[n]}.$$
That is if $f$ is represented as a sum of monomials then we can easily calculate $S(f)$.
On the other hand, if $f$ is represented as a tree of nested sums and products then, as I understood, the calculation of $S(f)$ can be hard. Namely, elements of $\Bbb F$ can be considered as Boolean constants. Using equalities $x \wedge y=xy$ and $x\vee y=x+y-xy$, and $\neg x=1-x$ we can consider Boolean formulas depending on $x_1,\dots, x_n$ as as polynomials from $\Bbb F[x_1,\dots,x_n]$ and vise versa. Then $S(f)=1$ iff the Boolean formula corresponding to $f$ has an odd number of variable assignments making it true.
Ryan Williams noted here that “the problem "Parity-SAT" (often written as $\oplus SAT$ in the literature) is the problem of determining whether or not a given Boolean formula has an odd number of assignments. It is well-studied, and is complete for the class $\oplus P$ which contains all languages of the form {$x ~|~ $ there are an odd number of accepting computation paths in $N(x)$}, where $N$ is a nondeterministic polynomial time machine”. See here about the complexity class $\oplus P$. In particular, it contains the graph isomorphism problem, which is not known to be solvable in polynomial time nor to be NP-complete. On the other hard, Parity SAT is NP-hard under randomized reductions, see [VV, p.92].
References
[VV] L.G. Valiant, V.V. Vazirani, NP is as easy as detecting unique solutions, Theoretical Computer Science 47 (1986) 85–93.