# Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity

Let $$n$$ be a large positive integer. Give a nonempty collection $$\mathcal S$$ of subsets of $$[n] := \{1,2,\ldots,n\}$$, define an inner-product on $$\mathbb R^n$$ by

$$\begin{eqnarray} \langle x,y\rangle_{\mathcal S} := \sum_{S \in \mathcal S}x_S y_S, \text{ for all }x,y \in \{\pm 1\}^n. \end{eqnarray}$$

where $$x_S := \prod_{i \in S}x_i$$. Fix a vector $$x \in \mathbb R^n$$, and if it helps, assume that $$x$$ has a large number (say $$n - O(\sqrt n)$$) of "small" components (compared to the absolute-value largest component). Let $$c(\mathcal S)$$ be the worst-case time complexity for computing $$\langle x,y\rangle_{\mathcal S}$$, for arbitrary $$y \in \{\pm 1\}^n$$. By using a naive algorithm, we always have the (typically horrible!) upper-bound

$$c(\mathcal S) = O(|\mathcal S|) = O(2^n).$$

Moreover, this upper-bound is attained when $$\mathcal S$$ is made of all singletons of $$[n]$$.

Question 1. Let $$\mathcal S_{n,d}$$ be the collection of all subsets of $$[n]$$ with $$d$$ or fewer elements. What is a good estimate for $$c(S_{n,d})$$ and which algorithm realizes it ?

Question 2. Is there any hope that $$c(\mathcal S_{n,d}) = O(n)$$.

Note that a naive implementation would give an algorithm where $$c(\mathcal S_{n,d}) = O(|\mathcal S_{n,d}|) = O(\sum_{\ell=0}^d {n \choose \ell})$$, which can be very large for when $$n$$ and $$d$$ are large.

Queston 3. Given $$n \ll m \ll 2^n$$, is it possible to construct $$\mathcal S$$ such that $$c(\mathcal S) = O(n)$$ (or perhaps $$O(n^2)$$) ?

Let $$z$$ be the coordinate-wise product of $$x$$ and $$y$$; that is, $$z_i = x_i y_i$$ for all $$i$$. Then we need to compute $$\sum_{S\in {\cal S}} z_S$$.

Q1: We can solve the problem using dynamic programming. Let $$T[i,j] = \sum\limits_{\substack{S\subseteq\{1,\dots, i\}\\|S|=j}} z_S$$. Then $$T[i,j] = T[i-1,j-1] \cdot z_i + T[i-1,j]$$. It's straightforward to write initialization formulas. The running time is $$O(nd)$$ assuming that all arithmetic operations take one unit of time.

Q3: Assume that $$n = 2k$$. Partition $$\{1,\dots, n\}$$ into $$k$$ groups $$G_1,\dots, G_k$$ of size 2 each; e.g. group $$G_i = \{2i-1,2i\}$$. Let $${\cal S}$$ be the family of sets $$S$$ that contain exactly one element from each $$G_i$$. Clearly, $$|{\cal S}| = 2^k$$. However, $$\sum_{S\in {\cal S}} z_S = \prod_{i=1}^k \sum_{j\in G_i}z_j.$$ can be computed in linear time.

Disclaimer. This is just to provide some details for Yuri's nice response to Q3, and generalize it to arbitrary group sizes.

Let $$n=p_1 + \ldots + p_k$$ be a partition of $$n$$ in to $$k \ge 1$$ positive integers. Partition the set $$[n]$$ into $$k$$ groups $$G_1,\ldots,G_k$$, with sizes $$|G_i| = p_i$$. By the product-of-sums rule, one has

$$\prod_{i=1}^k \sum_{j \in G_i} z_j = \sum_{(j_1,\ldots,j_k) \in G_1 \times \ldots \times G_k} z_{j_1,\ldots,j_k} = \sum_{S \in \mathcal S} z_S =: \langle x,y\rangle_{\mathcal S},$$

where $$\mathcal S = \mbox{setify}(G_1 \times \ldots \times G_k) := \{\mbox{set}(X) \mid X \in G_1 \times \ldots \times G_k\}$$ is the collection of subsets of $$[n]$$ which contain exactly one item from each group $$G_i$$. Moreover, since the $$G_i$$'s are pairwise disjoint, it is clear that $$\mathcal S$$ is in fact isomorphic to $$G_1 \times \ldots \times G_k$$ and so $$|\mathcal S| = p_1\ldots p_k$$.

In particular, if $$n$$ is even, then we can take $$p=2$$ and $$k = n/2$$ to recover the construction in Yuri's answer, where $$|\mathcal S| = 2\ldots 2\text{ (k times)} = 2^k = 2^{n/2}$$.