<p>Let <span class="math-container">$z$</span> be the coordinate-wise product of <span class="math-container">$x$</span> and <span class="math-container">$y$</span>; that is, <span class="math-container">$z_i = x_i y_i$</span> for all <span class="math-container">$i$</span>. Then we need to compute <span class="math-container">$\sum_{S\in {\cal S}} z_S$</span>.</p>
<p><strong>Q1:</strong> We can solve the problem using dynamic programming. Let <span class="math-container">$T[i,j] = \sum\limits_{\substack{S\subseteq\{1,\dots, i\}\\|S|=j}} z_S$</span>. Then <span class="math-container">$T[i,j] = T[i-1,j-1] \cdot z_i + T[i-1,j]$</span>. It's straightforward to write initialization formulas. The running time is <span class="math-container">$O(nd)$</span> assuming that all arithmetic operations take one unit of time.</p>
<p><strong>Q3:</strong> Assume that <span class="math-container">$n = 2k$</span>. Partition <span class="math-container">$\{1,\dots, n\}$</span> into <span class="math-container">$k$</span> groups <span class="math-container">$G_1,\dots, G_k$</span> of size 2 each; e.g. group <span class="math-container">$G_i = \{2i-1,2i\}$</span>. Let <span class="math-container">${\cal S}$</span> be the family of sets <span class="math-container">$S$</span> that contain exactly one element from each <span class="math-container">$G_i$</span>. Clearly, <span class="math-container">$|{\cal S}| = 2^k$</span>. However,
<span class="math-container">$$\sum_{S\in {\cal S}} z_S = \prod_{i=1}^k \sum_{j\in G_i}z_j.$$</span>
can be computed in linear time.</p>

CC BY-SA 4.0
2023-03-09T22:02:12.473Z
2023-03-09T22:02:12.473Z
Yury
<p><strong>Disclaimer.</strong> This is just to provide some details for Yuri's nice response to <strong>Q3</strong>, and generalize it to arbitrary group sizes.</p>
<hr />
<p>Let <span class="math-container">$n=p_1 + \ldots + p_k$</span> be a partition of <span class="math-container">$n$</span> in to <span class="math-container">$k \ge 1$</span> positive integers. Partition the set <span class="math-container">$[n]$</span> into <span class="math-container">$k$</span> groups <span class="math-container">$G_1,\ldots,G_k$</span>, with sizes <span class="math-container">$|G_i| = p_i$</span>. By the product-of-sums rule, one has</p>
<p><span class="math-container">$$
\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},
$$</span></p>
<p>where <span class="math-container">$\mathcal S = \mbox{setify}(G_1 \times \ldots \times G_k) := \{\mbox{set}(X) \mid X \in G_1 \times \ldots \times G_k\}$</span> is the collection of subsets of <span class="math-container">$[n]$</span> which contain exactly one item from each group <span class="math-container">$G_i$</span>. Moreover, since the <span class="math-container">$G_i$</span>'s are pairwise disjoint, it is clear that <span class="math-container">$\mathcal S$</span> is in fact isomorphic to <span class="math-container">$G_1 \times \ldots \times G_k$</span> and so <span class="math-container">$|\mathcal S| = p_1\ldots p_k$</span>.</p>
<p>In particular, if <span class="math-container">$n$</span> is even, then we can take <span class="math-container">$p=2$</span> and <span class="math-container">$k = n/2$</span> to recover the construction in Yuri's answer, where <span class="math-container">$|\mathcal S| = 2\ldots  2\text{ (k times)} = 2^k = 2^{n/2}$</span>.</p>

CC BY-SA 4.0
2023-03-10T11:04:33.057Z
2023-03-10T14:05:05.493Z
2023-03-10T14:05:05.493Z
dohmatob
<p>Let <span class="math-container">$n$</span> be a large positive integer. Give a nonempty collection <span class="math-container">$\mathcal S$</span> of subsets of <span class="math-container">$[n] := \{1,2,\ldots,n\}$</span>, define an inner-product on <span class="math-container">$\mathbb R^n$</span> by</p>
<p><span class="math-container">\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}</span></p>
<p>where <span class="math-container">$x_S := \prod_{i \in S}x_i$</span>. Fix a vector <span class="math-container">$x \in \mathbb R^n$</span>, and if it helps, assume that <span class="math-container">$x$</span> has a large number (say <span class="math-container">$n - O(\sqrt n)$</span>) of &quot;small&quot; components (compared to the absolute-value largest component). Let <span class="math-container">$c(\mathcal S)$</span> be the worst-case time complexity for computing <span class="math-container">$\langle x,y\rangle_{\mathcal S}$</span>, for arbitrary <span class="math-container">$y \in \{\pm 1\}^n$</span>. By using a naive algorithm, we always have the (typically horrible!) upper-bound</p>
<p><span class="math-container">$$
c(\mathcal S) = O(|\mathcal S|) = O(2^n).
$$</span></p>
<p>Moreover, this upper-bound is attained when <span class="math-container">$\mathcal S$</span> is made of all singletons of <span class="math-container">$[n]$</span>.</p>
<p><strong>Question 1.</strong> Let <span class="math-container">$\mathcal S_{n,d}$</span> be the collection of all subsets of <span class="math-container">$[n]$</span> with <span class="math-container">$d$</span> or fewer elements. What is a good estimate for <span class="math-container">$c(S_{n,d})$</span> and which algorithm realizes it ?</p>
<p><strong>Question 2.</strong> Is there any hope that <span class="math-container">$c(\mathcal S_{n,d}) = O(n)$</span>.</p>
<p>Note that a naive implementation would give an algorithm where <span class="math-container">$c(\mathcal S_{n,d}) = O(|\mathcal S_{n,d}|) = O(\sum_{\ell=0}^d {n \choose \ell})$</span>, which can be very large for when <span class="math-container">$n$</span> and <span class="math-container">$d$</span> are large.</p>
<p><strong>Queston 3.</strong> Given <span class="math-container">$n \ll m \ll 2^n$</span>, is it possible to construct <span class="math-container">$\mathcal S$</span> such that <span class="math-container">$c(\mathcal S) = O(n)$</span>  (or perhaps <span class="math-container">$O(n^2)$</span>) ?</p>

<ds.algorithms><circuit-complexity><ds.data-structures><linear-algebra><randomized-algorithms>
Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity
dohmatob
# Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity

(Asked by: username_0 on 2023-03-08)

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

**Tags:** ds.algorithms, circuit-complexity, ds.data-structures, linear-algebra, randomized-algorithms


---

## 2 answers

### Answer by username_1 on 2023-03-09. Score: 4 | Accepted answer

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 by username_0 on 2023-03-10. Score: 1

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


---

