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

Question

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)$) ?

Answer 1

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.

Answer 2

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}$.