0
$\begingroup$

It was previously asked 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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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: arxiv.org/pdf/1002.0562.pdf $\endgroup$
    – domotorp
    Sep 21, 2021 at 19:03
  • $\begingroup$ @domotorp Thanks for pointing this out, I cleared this up in the question now. Also, I'll have a look at the reference. $\endgroup$
    – Cornelius Brand
    Sep 21, 2021 at 20:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Sep 22, 2021 at 2:05
  • $\begingroup$ @Chandra What do you mean by well-linked? $\endgroup$
    – domotorp
    Sep 22, 2021 at 6:36
  • $\begingroup$ 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). $\endgroup$
    – Chandra Chekuri
    Sep 22, 2021 at 12:05

0

Reset to default

Your Answer

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