Taking inspiration from sorting networks, I was wondering if another prominent algorithm can be implemented in the same fashion: finding the longest increasing sub-sequence (LIS), Input is given as wires $x_1,\dots, x_n,$ and we want to design a circuit that solves it. with the standard algorithm using $O(n \lg n)$ comparisons to find the sub-sequence, one would aspire the network to have a logarithmic number of layers in $n$.
One way of conceptualising a circuit: we assume wlog that input wires $x_1,\dots,x_n$ are positive, and use $0$ as an special value that designates a "removed" element. The logical elements $f$ receive two inputs and give two outputs, obeying $f(a,b) = (a,b)$ if $a\le b,$ and $f(a,b) = (a,0),$ where $0$ designates that $b$ is deleted.
We want to pass the input through multiple layers, such that the non-zero output wires $y_1,\dots,y_n$ correspond to a longest-common subsequence.
An example illustration with inputs $x_1,x_2,x_3,x_4$ and outputs $z_1,z_2,z_3,z_4$:
\begin{align} \text{layer 1 ($x\to y$): } &(y_1,y_2) := f(x_1,x_2) , &&(y_3,y_4) := f(x_3,x_4) \\ \text{layer 2 ($y\to z$): } &(z_2,z_3) := f(y_2,x_3), &&(z_1,z_4):= (y_1,y_4) \end{align} Here are some sample input/outputs going from inputs $x_i$'s to $y_i$'s, and finally output $z_i$'s: \begin{align} x=(1,6,3,2)\to y=(1,6,3,0) \to z=(1,6,0,0) \implies \text{ non-zero $z$=} (1,6) \\ x=(5,1,7,2) \to y=(5,0,7, 0) \to z=(5, 0, 7, 0) \implies \text{ non-zero $z$=} (5,7) \\ x=(5,7,2,3) \to y=(5,7,2, 3) \to z=(5, 7, 0, 3) \implies \text{ non-zero $z$=} (5,7,3) \\ \end{align}
So the first two inputs are correctly computed, by the third output ($5,7,3$) is not in non-decreasing order. Intuitively, in order to compute LIS, one needs to condition on length of sub-sequence so far are not a "local" decision, like the comparison elements in sorter networks.
Any ideas if such a LIS circuit is feasible with the proposed element? If not, can some other element be added to make it a feasible?
As suggested by @Neal Young in the comments, I read the claims of this paper. From my understanding, the work of a parallel algorithm is the overall number of operations, and the span is the longest chain of dependent operations. Any circuit would be trivially leading to a parallel algorithm, with the number of elements used in the circuit corresponding to work, and number of layers corresponding to span of the algorithm. To the best of my understanding, the opposite does not hold: not every parallel algorithm might can be converted to a circuit unless we loosen the concept a bit.
Therefore, the one-sided connection implies that if there were any straightforward circuit designs, there would have been an $O(n \lg n)$-work and $\tilde{O}(\lg n)$-span LIS parallelism. To my surprise, the mentioned paper4 give only $O(k)$-span parallelism where $k$ is the LIS length, which is substantially greater a "shallow circuit" $\tilde{O}(\lg n)$ when the LIS length is comparable to $n$.
