We are given an array of variables $A$, along with a matrix $M$. The elements of the matrix $M$ are composed of sums of the variables in $A$. We are allowed to pre-process $A$ in order to find a quick way to obtain the entries of $M$ - in other words, the fastest way to obtain sums of the variables in $A$. We do know which variables we must use for each sum in advance. Also, the matrix rows follow the rule that each element of the array will be used in exactly one sum in each row of the matrix.

So, for example, we are given the array:

$$(x_1, x_2, x_3, x_4, x_5)$$

Then, we are given a matrix:

$$\begin{pmatrix} x_2 + x_3 & x_1 + x_4 + x_5 \\ x_1 + x_2 + x_5 & x_3 + x_4 \\ \end{pmatrix}$$

We are allowed to pre-compute using as many resources as we like. The goal is to get a circuit that computes the sums of the matrix using as little resources as possible (but with as much pre-computation as one wants).

The matrix will be an $n/\alpha \times \alpha$ sized matrix of non-negative integers less than $\alpha$, with $\alpha \approx \log \log \log n$. The array will contain $n$ elements.

I'm wondering how well we can do in the worst case or in the average case.

  • $\begingroup$ Can the same variable appear twice in the same sum? If yes, is multiplication allowed or should it be done with iterated addition? $\endgroup$
    – xavierm02
    Apr 25, 2018 at 11:59
  • $\begingroup$ The case where you do not allow variable repetition seems a bit easier, and can be rephrased as follows: Given $A\subseteq\mathcal P(X)$, what's the cardinal of the smallest $B$ such that $A\subseteq B$ and $\forall Y\in B, Y\not=\emptyset\implies \exists y \in Y, Y\setminus\{y\}\in B$. Intuitively, $X$ is the set of variables, $A$ is the set (multiset if we allow repetitions) representing sums that we want to compute, $B$ is the set of all sums we will actually compute. To compute the sum of $Y$, you first compute the sum of $Y\setminus \{y\}$ and then add $y$ to it. $\endgroup$
    – xavierm02
    Apr 25, 2018 at 12:02
  • $\begingroup$ @xavierm02: Variable repetition is not allowed. My approach seems somewhat similar to yours... I tried building sets of the variables to correspond with the sums in the matrix, but I'm having trouble finding a systematic approach that is efficient. In fact, I'm not even sure what efficient is for this problem. $\endgroup$
    – Matt Groff
    Apr 25, 2018 at 16:58
  • 1
    $\begingroup$ @xavierm02: I just thought that I should clarify: Variable repetition is not allowed, but the actual values may repeat. For example, $x_1=5, x_3=5$ is allowed. So we do have multisets of values, which seems to complicate things. $\endgroup$
    – Matt Groff
    Apr 25, 2018 at 17:14


Your Answer

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