JHM was working at a light festival. We worked the setup, worked the festival, then worked the tear down. Honestly it was fun, alot of smiles, but we didn't really make as much money as we wanted... but that's okay.

The problem with working is that we cannot focus our mind or energies on our research projects. This is life. It's partly why we fear having children, because they demand alot of physical and cognitive energies. Over the last 14+ years, our math projects have been our children. [RIP Steven Brody Stevens].

Work In Progress: Algorithmic Complexity

So where is our research at? In general we have projects in TopSing, SR, MCG, DT, OT, Sponge, but we also have an idea brewing about computational complexity. We want to prove hard lower bounds for the complexity of certain computational problems. From our perspective the most important problem is SUBSET-SUM and especially ZERO SUBSET SUM over integers, although this problem has many more solutions over group rings $\mathbf{Z} \Gamma$ for various discrete groups $\Gamma$.

The general problem is: given a finite subset $S \subset \mathbf{Z}$ of integers, decide whether there exists a zero subset sum. Does there exist a finite subset $S' \subset S$ such that $$\sum_{s' \in S'} s'=0.$$

The question we want to answer: is every algorithm which solves ZERO SUBSET SUM basically equivalent to the standard Meet-In-The-Middle algorithm? I.e. is there essentially only one algorithm to solve ZERO SUBSET SUM?

1. Our email exchanges with Craig Alan Feinstein and reading his papers have given us the following idea: Every deterministic algorithm is a composition of random search and deterministic function evaluation.

This is somewhat a trivial observation, but we think it's key for proving hard lower bounds for the computational complexity of various algorithms. In otherwords, the meet-in-the-middle algorithm for SUBSET-SUM is an algorithm having such a pattern. But our point is that every algorithm which tries to solve SUBSET-SUM will necessarily have the same pattern: it is a composition of a deterministic function (like SUM) with random unstructured search over subsets.

Remark. In the literature, it appears that "random search" is called "nondeterministic search".

For example, does the set of integers $$\{ -20, -17, -3, 9, 10, 133 \}$$ contain a zero subset sum? Here the answer is No, but how do we determine this? Only by examining all the subset sums of the $2^6=64$ subsets. So "one by one" we look through the subsets, evaluating their SUM, and deciding whether the sum returns a zero or not.

There is an expression from Sherlock Holmes which we bear in mind in "The House of Fear". Sherlock says that, "at this moment he suspects no one and everyone." And this ambiguity reflects the necessary uncertainty of incomplete information. Every algorithm has the same problem, it simultaneous suspects everyone and nobody unless there is determinate information to the contrary.

This is somewhat trivial discussion. But our idea is that there is nothing behind it! It doesn't get any more trivial, neither does it get any more complicated.

1. There is another idea. It begins with function composition $h=g\circ f$ which is the most important operation in mathematics. Here $f,g,h$ are supposed to be functions. But we understand pragmatically that, although the functions are equal in the sense of returning identical outputs for given inputs, the evaluation of the function is quite different from the RHS compared to the LHS. In otherwords, the equality $h=g\circ f$ says the functions are equal, but the presence of $\circ$ shows that the evaluation/computation of these functions are distinct!

So the complexity of $h$ and $g\circ f$ are not necessarily identical. The problem here is how to measure/quantify the "complexity" of functions as depending on their representation. Concretely we should expect the complexity of $h$ and $g\circ f$ to be distinct although the functions are identical set-theoretically.

Let's try to be more specific. In optimal transport we learn how measures $\pi$ on products $X\times Y$ can represent "functions" $f: X \to Y$. Functions are correlations from source to target (i.e. from input to output). So the question becomes:

What is correct definition of the composition $\pi_2 \circ \pi_1 \in \mathscr{M}(X_1 \times X_3)$ of measures $\pi_1 \in \mathscr{M}(X_1 \times X_2)$ and $\pi_2 \in \mathscr{M}(X_2\times X_3)$ ?

The idea is this composition will correspond to function composition when the measures $\pi$ represent the graphs of measurable functions.

Recall: this idea arises in optimal transport when establishing the triangle inequality in Wasserstein spaces. In Villani's textbook the proof is achieved using "disintegration of measures" theorem. But is there a more general functorial construction?

There is also an exercise in Villani which uses Hahn Banach Separation theorem in the dual setting, but we admit we've never understood this argument. Maybe now is the time?

Ultimately we are trying to give a definite form or structure of the general algorithm which solves ZERO SUBSET SUM. This is interesting question given the recent ML results regarding matrix multiplication. The researchers were forced to define the "total space of all algorithms for matrix multiplication". But in this work they realized that multiplication is a tensor of linear algebra. They therefore were optimizing and searching over the space of tensors which represent matrix multiplication. And it's interesting but tensors differ one from another by zero subset sums! This is a basic representation result that we remember reading from David Eisenbud's "Commutative Algebra with a View Towards Algebraic Geometry".