<p>It was <a href="https://cstheory.stackexchange.com/questions/26021/minimum-tree-width-of-circuit-for-majority">previously asked</a> if there exist Boolean circuits of treewidth <span class="math-container">$O(\log n)$</span> that compute the majority function <span class="math-container">$\text{MAJ}_n$</span> on <span class="math-container">$n$</span> inputs. While a construction using online algorithms and the related concept of online-width affirms this, in the original question the point was raised whether any of the known quasilinear sorting networks (which induce circuits for <span class="math-container">$\text{MAJ}_n$</span>) share this property. As far as I'm aware, this was left unanswered.</p>
<p>Here, the treewidth of a sorting network is the treewidth of the underlying undirected graph that has as vertices the comparators, and each vertex has degree four (corresponding to the two inputs and outputs).</p>
<p>Hence, as a follow-up question:</p>
<blockquote>
<p>Are there sorting networks of size <span class="math-container">$n\cdot \text{polylog}(n)$</span> and (poly)logarithmic treewidth?</p>
</blockquote>
<p>More generally, I am interested in sorting networks of size <span class="math-container">$s$</span> and treewidth <span class="math-container">$\tau$</span> such that <span class="math-container">$s\tau^2 \leq n^{1.99}$</span>. Conversely:</p>
<blockquote>
<p>Are there lower bounds that rule out such networks?</p>
</blockquote>
<p>One thing I could think of is that sorting networks should have high expansion, but that is vague.</p>

CC BY-SA 4.0
2021-09-21T19:03:31.417Z
I'm not sure how you define the treewidth of a sorting network, but in this paper there is a thickness parameter for sorting that might be relevant; they also prove a lower bound: https://arxiv.org/pdf/1002.0562.pdf
domotorp
CC BY-SA 4.0
2021-09-21T20:39:25.510Z
@domotorp Thanks for pointing this out, I cleared this up in the question now. Also, I'll have a look at the reference.
Cornelius Brand
CC BY-SA 4.0
2021-09-22T02:05:28.223Z
I believe that treewidth of any sorting network viewed as a graph has to be $\Omega(n)$ because the input nodes (terminals) form a well-linked set in the graph.
Chandra Chekuri
CC BY-SA 4.0
2021-09-22T06:36:47.807Z
@Chandra What do you mean by well-linked?
domotorp
CC BY-SA 4.0
2021-09-22T12:05:33.947Z
In a graph $G=(V,E)$ a set of vertices $X \subseteq V$ is said to be well-linked if for any $S \subseteq V$ we have $|\delta(S)| \ge \min\{|X \cap S|, |(V-S)\cap X|\}$. In other words the graph has no small edge-separator for $X$. This is like expansion but only for the subset $X$. It is known that $G$ has treewidth $\tau$ iff $G$ has a well-linked set of size $\Omega(\tau)$ (in constant degree graphs, otherwise one has to work with node expansion).
Chandra Chekuri
<reference-request><lower-bounds><sorting><treewidth>
Low-Treewidth Sorting Networks
Cornelius Brand
# Low-Treewidth Sorting Networks

(Asked by: username_0 on 2021-09-21)

It was [previously asked](https://cstheory.stackexchange.com/questions/26021/minimum-tree-width-of-circuit-for-majority) if there exist Boolean circuits of treewidth $O(\log n)$ that compute the majority function $\text{MAJ}\_n$ on $n$ inputs. While a construction using online algorithms and the related concept of online-width affirms this, in the original question the point was raised whether any of the known quasilinear sorting networks (which induce circuits for $\text{MAJ}\_n$) share this property. As far as I'm aware, this was left unanswered.

Here, the treewidth of a sorting network is the treewidth of the underlying undirected graph that has as vertices the comparators, and each vertex has degree four (corresponding to the two inputs and outputs).

Hence, as a follow-up question:

> Are there sorting networks of size $n\cdot \text{polylog}(n)$ and (poly)logarithmic treewidth?

More generally, I am interested in sorting networks of size $s$ and treewidth $\tau$ such that $s\tau^2 \leq n^{1.99}$. Conversely:

> Are there lower bounds that rule out such networks?

One thing I could think of is that sorting networks should have high expansion, but that is vague.

**Tags:** reference-request, lower-bounds, sorting, treewidth

> **Comments:**
> **username_1**: I'm not sure how you define the treewidth of a sorting network, but in this paper there is a thickness parameter for sorting that might be relevant; they also prove a lower bound: https://arxiv.org/pdf/1002.0562.pdf  
> **username_0**: @username_1 Thanks for pointing this out, I cleared this up in the question now. Also, I'll have a look at the reference.  
> **username_2**: I believe that treewidth of any sorting network viewed as a graph has to be $\Omega(n)$ because the input nodes (terminals) form a well-linked set in the graph.  
> **username_1**: @Chandra What do you mean by well-linked?  
> **username_2**: In a graph $G=(V,E)$ a set of vertices $X \subseteq V$ is said to be well-linked if for any $S \subseteq V$ we have $|\delta(S)| \ge \min\{|X \cap S|, |(V-S)\cap X|\}$. In other words the graph has no small edge-separator for $X$. This is like expansion but only for the subset $X$. It is known that $G$ has treewidth $\tau$ iff $G$ has a well-linked set of size $\Omega(\tau)$ (in constant degree graphs, otherwise one has to work with node expansion).  

---

## 0 answers

