Constant-depth sorting networks
summary
Considers sorting under k-sorting networks where each unit sorts k positions in one layer, uses the 0-1 principle and a new access technique to prove exact and asymptotic arities for small constant depth. Shows d=1 and d=2 force k=n, d=3 requires k=ceil(n/2), and d=4 admits k = Theta(n^{2/3}). Gives a general lower bound k >= n / 2^{2/d} (rounded), and explains why these constants prevent the simple recursive scheme from improving the classic O(log^2 n) depth.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 6:39Sorting networks
- 7:14Depth
- 10:35Case Sorting
- 12:54Theory
- 16:53Solution
- 24:33Minimum Key
- 26:42Subnotation
- 29:13Zeroone principle
- 29:52Access technique
related talks
27mA Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion
33mLucky Talk: Exponential Separation of Information and Communication
01h 09mInformation Theory in Computational Complexity IV
30mStreaming Lower Bounds for Approximating MAX-CUT
01h 07mWhere the Hard Things Are
27mInformation Complexity for Multi-Party NIH Communication
32mA Finite Alternation Result for Reversible Boolean Circuits
01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting Complexity