HackerPapers

arXiv:2012.04400cs.DS

An Answer to the Bose-Nelson Sorting Problem for 11 and 12 Channels

Jannis Harder

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

We show that 11-channel sorting networks have at least 35 comparators and that 12-channel sorting networks have at least 39 comparators. This positively settles the optimality of the corresponding sorting networks given in The Art of Computer Programming vol. 3 and closes the two smallest open instances of the Bose-Nelson sorting problem. We obtain these bounds by generalizing a result of Van Voorhis from sorting networks to a more general class of comparator networks. From this we derive a dynamic programming algorithm that computes the optimal size for a sorting network with a given number of channels. From an execution of this algorithm we construct a certificate containing a derivation of the corresponding lower size bound, which we check using a program formally verified using the Isabelle/HOL proof assistant.

arXiv comments
v1: Revised attribution of previous results in the introduction v2: Fixed labels in Figure 3
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Dec 2020 to Dec 2020. Found in 1 HN submission from Dec 2020 to Dec 2020. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Ask HN: What's the best paper you've read in 2020? 1 comment

    • I haven't exactly read many this year, but I really liked "An Answer to the Bose-Nelson Sorting Problem for 11 and 12 Channels" [1]. It describes many interesting algorithmic tricks to establish a lower bound for an easy to understand problem. Not exactly immediately practical…

      NieDzejkobView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.