<p>Taking inspiration from <a href="https://en.wikipedia.org/wiki/Sorting_network" rel="nofollow noreferrer">sorting networks</a>, I was wondering if another prominent algorithm can be implemented in the same fashion: finding the <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence" rel="nofollow noreferrer">longest increasing sub-sequence (LIS)</a>,
Input is given as wires <span class="math-container">$x_1,\dots, x_n,$</span> and we want to design a circuit that solves it. with the standard algorithm using <span class="math-container">$O(n \lg n)$</span> comparisons to find the sub-sequence, one would aspire the network to have a logarithmic number of layers in <span class="math-container">$n$</span>.</p>
<p>One way of conceptualising a circuit: we assume wlog that input wires <span class="math-container">$x_1,\dots,x_n$</span> are positive, and use <span class="math-container">$0$</span> as an special value that designates a &quot;removed&quot; element. The logical elements <span class="math-container">$f$</span> receive two inputs and give two outputs, obeying <span class="math-container">$f(a,b) = (a,b)$</span> if <span class="math-container">$a\le b,$</span> and <span class="math-container">$f(a,b) = (a,0),$</span> where <span class="math-container">$0$</span> designates that <span class="math-container">$b$</span> is deleted.</p>
<p>We want to pass the input through multiple layers, such that the non-zero output wires <span class="math-container">$y_1,\dots,y_n$</span> correspond to a longest-common subsequence.</p>
<blockquote>
<p>An example illustration with inputs <span class="math-container">$x_1,x_2,x_3,x_4$</span> and outputs <span class="math-container">$z_1,z_2,z_3,z_4$</span>:<br />
<a href="https://i.sstatic.net/xy3N1.png?s=256" rel="nofollow noreferrer"><img src="https://i.sstatic.net/xy3N1.png?s=256" alt="LIS circuit" /></a>
<span class="math-container">\begin{align} 
\text{layer 1 ($x\to y$): } &amp;(y_1,y_2) := f(x_1,x_2) , &amp;&amp;(y_3,y_4) := f(x_3,x_4) \\
\text{layer 2 ($y\to z$): } &amp;(z_2,z_3) := f(y_2,x_3), &amp;&amp;(z_1,z_4):= (y_1,y_4) 
\end{align}</span>
Here are some sample input/outputs going from inputs <span class="math-container">$x_i$</span>'s to <span class="math-container">$y_i$</span>'s, and finally output <span class="math-container">$z_i$</span>'s:
<span class="math-container">\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}</span></p>
</blockquote>
<p>So the first two inputs are correctly computed, by the third output (<span class="math-container">$5,7,3$</span>) 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 &quot;local&quot; decision, like the comparison elements in sorter networks.</p>
<p>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?</p>
<p>As suggested by @Neal Young in the comments, I read the claims of
<a href="https://arxiv.org/pdf/2208.09809.pdf" rel="nofollow noreferrer">this paper</a>. From my understanding, the <em>work</em> of a parallel algorithm is the overall number of operations, and the <em>span</em> 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.</p>
<p>Therefore, the one-sided connection implies that if there were any straightforward circuit designs, there would have been an <span class="math-container">$O(n \lg n)$</span>-work and <span class="math-container">$\tilde{O}(\lg n)$</span>-span LIS parallelism. To my surprise, the mentioned paper<a href="https://arxiv.org/pdf/2208.09809.pdf" rel="nofollow noreferrer">4</a> give only <span class="math-container">$O(k)$</span>-span parallelism where <span class="math-container">$k$</span> is the LIS length, which is substantially greater a &quot;shallow circuit&quot; <span class="math-container">$\tilde{O}(\lg n)$</span> when the LIS length is comparable to <span class="math-container">$n$</span>.</p>

CC BY-SA 4.0
2023-03-14T12:09:43.293Z
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?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-03-14T12:27:57.390Z
Is it more clear now @a3nm
AmeerJ
CC BY-SA 4.0
2023-03-14T19:37:08.210Z
You might do a literature search and summarize what is known in your post.  E.g.  the authors of [this 2022 paper](https://arxiv.org/abs/2208.09809) "are unaware of any parallel LIS algorithm that has $O(n\log n)$ work and non-trivial parallelism".
Neal Young
CC BY-SA 4.0
2023-03-14T20:14:15.937Z
@AmeerJ: yes, thanks!
Antoine Amarilli 'a3nm'
<sorting-network>
Circuit computing Longest Increasing Sub-sequence (LIS)
AmeerJ
# Circuit computing Longest Increasing Sub-sequence (LIS)

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

Taking inspiration from [sorting networks](https://en.wikipedia.org/wiki/Sorting_network), I was wondering if another prominent algorithm can be implemented in the same fashion: finding the [longest increasing sub-sequence (LIS)](https://en.wikipedia.org/wiki/Longest_increasing_subsequence),
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](https://i.sstatic.net/xy3N1.png?s=256)](https://i.sstatic.net/xy3N1.png?s=256)
> \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](https://arxiv.org/pdf/2208.09809.pdf). 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 paper[4](https://arxiv.org/pdf/2208.09809.pdf) 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$.

**Tags:** sorting-network
> **Comments:**
> **username_1**: 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?  
> **username_0**: Is it more clear now @a3nm  
> **username_2**: You might do a literature search and summarize what is known in your post.  E.g.  the authors of [this 2022 paper](https://arxiv.org/abs/2208.09809) "are unaware of any parallel LIS algorithm that has $O(n\log n)$ work and non-trivial parallelism".  
> **username_1**: @AmeerJ: yes, thanks!  

---

## 0 answers

