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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.