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$:
LIS circuit \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$.

  • $\begingroup$ Hi, sorry some points are not very clear to me in your question. What is "f(a,b)=(a,b) if a≤b, and f(a,b)=(a,0),"? What are the input gates of the circuit? What is the output? $\endgroup$
    – a3nm
    Mar 14, 2023 at 12:09
  • $\begingroup$ Is it more clear now @a3nm $\endgroup$
    – AmeerJ
    Mar 14, 2023 at 12:27
  • 3
    $\begingroup$ You might do a literature search and summarize what is known in your post. E.g. the authors of this 2022 paper "are unaware of any parallel LIS algorithm that has $O(n\log n)$ work and non-trivial parallelism". $\endgroup$
    – Neal Young
    Mar 14, 2023 at 19:37
  • $\begingroup$ @AmeerJ: yes, thanks! $\endgroup$
    – a3nm
    Mar 14, 2023 at 20:14


Your Answer

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

Browse other questions tagged or ask your own question.