4
$\begingroup$

The famous AKS sorting network allows one to sort $N$ elements via a circuit composed out of comparator gates, where the circuit has size $\mathcal{O}(n \log n)$ and depth $\mathcal{O}(\log n)$. The latest discussion of the hidden constants behind this construction that I could find were in the Zig-Zag sorting paper, where (if I correctly understood) the author states that $13 613 047$ is the currently best known constant.

Question: Is this, as of 2020, still the best known hidden constant for a deterministic oblivious sorting algorithm with optimal complexity?

$\endgroup$
  • $\begingroup$ The Zig-Zag paper seems to say it isn’t $O(\log n)$ depth, so unfortunately I don’t think it applies as a solution to your question. $\endgroup$ – Geoffrey Irving Aug 17 at 19:27
  • $\begingroup$ Oh yes Zig-Zag has depth $\mathcal{O}(n)$. It was just the latest paper which discussed the hidden constants behind AKS as well. Since this is already over 5 years ago, I was wondering whether the hidden constants improved (for AKS). $\endgroup$ – Cryptonaut Aug 18 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.