Depth-13 Sorting Networks for 28 Channels

Basic Information

• Paper ID: 2511.04107
• Title: Depth-13 Sorting Networks for 28 Channels
• Author: Chengu Wang (wangchengu@gmail.com)
• Classification: cs.DS (Data Structures and Algorithms), cs.DM (Discrete Mathematics)
• Publication Date: November 6, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2511.04107

Abstract

This paper establishes new depth upper bounds for sorting networks with 27 and 28 channels, improving the previous best bounds from depth 14 to depth 13. The 28-channel network is constructed through reflective symmetry, combining high-quality prefixes from 16-channel and 12-channel networks, extended greedily by individual comparators, and completed using a SAT solver for the remaining layers.

Research Background and Motivation

Problem Definition

The core problem addressed in this research is finding optimal-depth sorting networks for specific channel counts (27 and 28). A sorting network is a comparator network that sorts an input sequence into non-decreasing order, where depth is defined as the maximum number of comparators on any path from input to output.

Research Significance

1. Practical Application Value: Sorting networks have important applications in GPU sorting, FPGA systems, and hardware implementations of cryptographic protocols
2. Theoretical Significance: Software sorting networks serve as building blocks for oblivious sorting algorithms in secure computation and differential privacy systems
3. Algorithm Optimization: Although AKS networks achieve O(log n) depth asymptotically, the implicit large constants make them impractical for real applications

Limitations of Existing Methods

• Batcher's odd-even merge sort and bitonic sort have O((log n)²) depth, which is suboptimal
• AKS networks, while asymptotically optimal, have prohibitively large constant factors
• For moderate values of n (such as 27 and 28), the previous best upper bound was 14 layers, leaving room for improvement

Core Contributions

1. Breakthrough Improvement: Improved the depth upper bound for 27 and 28-channel sorting networks from 14 layers to 13 layers
2. Novel Construction Method: Proposed a divide-and-conquer construction strategy based on reflective symmetry, combined with 16+12 channel decomposition
3. Search Space Optimization: Developed two new techniques to reduce search space: reflective symmetry constraints and greedy single-comparator extension
4. Efficient Implementation: The entire computation completed in under 20 minutes on a Mac mini M2, with open-source code provided

Detailed Methodology

Task Definition

Input: An arbitrary sequence of comparable values on n channels Output: The sequence sorted in non-decreasing order Constraint: Minimize network depth (maximum number of comparators on any path from input to output)

Core Theoretical Foundations

Zero-One Principle

If a comparator network correctly sorts all 2^n boolean sequences, then it correctly sorts all sequences of arbitrary comparable values. This significantly simplifies the verification process.

Redundant Prefix Elimination

Search space pruning based on the following lemmas:

• Lemma 2: If output(P') ⊆ output(P) and P#S is a sorting network, then P'#S is also a sorting network
• Lemma 3: Extension of Lemma 2 through permutation symmetry
• Corollary 1: Complete redundancy elimination conditions combining permutation and negation operations

Construction Strategy

Three-Stage Construction Method

1. Prefix Combination Stage: Combine high-quality 5-layer prefix from 16-channel network with 5-layer prefix from 12-channel network
2. Greedy Extension Stage: Extend layer by layer with individual comparators to layer 6, maintaining an optimal candidate set
3. SAT Solving Stage: Use SAT solver to complete layers 7-13

Reflective Symmetry Exploitation

• Restrict search space to reflectively symmetric networks
• Perform symmetry pruning using the structure of centralized group C(ρn)
• Reflectively symmetric permutations form wreath product C₂ ≀ S_{n/2}

Technical Innovations

1. 16+12 Decomposition Strategy

Rationale for choosing 16+12 over 14+14 decomposition:

• Channels with power-of-two counts are typically more efficient
• Merging is most effective when both parts are similar in size
• 16-channel networks have excellent Van Voorhis prefixes available

2. Greedy Single-Comparator Extension

Traditional methods enumerate all possible symmetric layers, incurring enormous computational overhead. This paper innovatively:

• Adds comparators and their reflections individually
• Retains the best 64 candidates at each step (sorted by output set size)
• Significantly reduces computational complexity

3. Efficient Redundancy Detection

Developed two heuristic methods:

• Positive Example Detection: Randomly permute rows and check column coverage relationships
• Negative Example Filtering: Compare row and column sum sequences

Experimental Setup

Computational Environment

• Hardware: Mac mini M2, 16GB RAM
• SAT Solver: MiniSat
• Programming Language: Not explicitly specified
• Total Computation Time: Under 20 minutes

Prefix Generation

12-Channel Prefix

• Generate all non-redundant reflectively symmetric 5-layer prefixes through layer-by-layer extension
• Prefix counts per layer: 1 → 4 → 41 → 1502 → 11753 → 2164
• Select 4 prefixes with smallest output set sizes (sizes 34, 34, 35, 35)

16-Channel Prefix

• Use the first 5 layers of Van Voorhis sorting network
• Construct 4-dimensional hypercube structure
• Layer 5 performs symmetric comparisons on corresponding keys by Hamming weight

SAT Solving Configuration

• Employ optimization techniques from CCFE+19
• oneUp and oneDown encoding techniques
• Constraints for final two layers
• Channel permutation to minimize window size
• Parallel solving of 8 SAT instances

Experimental Results

Main Results

Successfully constructed a 28-channel 13-layer reflectively symmetric sorting network, with the complete network structure containing 13 layers and comparator configurations for each layer detailed in the paper.

Performance Analysis

• Computation Time Breakdown:
  • 12-channel 5-layer prefix search: 12 minutes
  • 16-channel 5-layer prefix search: 1 minute
  • SAT solving (8 instances in parallel): 0.5-5 minutes
  • Other steps: Nearly instantaneous

Verification Results

• All 8 best prefixes found feasible solutions
• Final network obtained by removing unused comparators
• Further optimized representation through input channel permutation

Corollary Results

Corollary 3: A 27-channel 13-layer sorting network also exists (derived straightforwardly from the 28-channel network)

Related Work

Historical Development

1. Classical Algorithms: Batcher's odd-even merge sort and bitonic sort (depth O((log n)²))
2. Theoretical Breakthrough: AKS networks achieving O(log n) depth and O(n log n) size
3. Small-Scale Optimization: Exact construction research for specific n values

Existing Techniques

• SorterHunter: Search tool exploiting reflective symmetry
• SAT Solving Methods: Encoding techniques by Codish et al.
• Prefix Search: Pruning strategies by Bundala and Závodnỳ

Directly Related Work

Ehlers Ehl17 improved 24-channel networks to 12 layers using similar prefix combination and SAT solving strategies; this paper extends the approach to larger scales.

Conclusions and Discussion

Main Conclusions

1. Successfully improved the depth upper bound for 27 and 28-channel sorting networks from 14 to 13
2. Demonstrated the effectiveness of reflective symmetry constraints and greedy extension
3. Provided an efficient implementation with reasonable computation time

Limitations

1. Method Limitations: Failed to achieve improvement for 18-channel networks
2. Search Strategy: Greedy extension may miss globally optimal solutions
3. Scale Limitations: Applicability of the method to larger-scale networks remains unknown

Future Directions

1. Machine Learning Integration: Use reinforcement learning to predict the most promising prefixes
2. Objective Function Optimization: Explore better greedy extension objectives than minimum output set
3. Larger Scales: Extend the method to 29-32 channel networks

In-Depth Evaluation

Strengths

1. Significant Practical Contribution: Breakthrough progress on an important practical problem
2. Strong Methodological Innovation: Greedy single-comparator extension is a novel and effective technique
3. Efficient Implementation: Complex search completed in 20 minutes, demonstrating strong practicality
4. Solid Theoretical Foundation: Based on mature symmetry theory and SAT solving techniques
5. Good Reproducibility: Complete open-source implementation provided

Weaknesses

1. Insufficient Theoretical Analysis: Lacks theoretical analysis of method complexity and convergence properties
2. Limited Experimental Scope: Addresses only 27 and 28 channels; generalization ability not fully verified
3. Insufficient Comparison: Limited comparison with other heuristic methods
4. Parameter Sensitivity: Does not analyze sensitivity of critical parameters (e.g., candidate set size of 64)

Impact

1. Academic Value: Provides new technical pathways for sorting network optimization
2. Practical Value: Direct significance for hardware design and cryptographic applications
3. Methodological Contribution: Greedy extension strategy may apply to other combinatorial optimization problems

Applicable Scenarios

1. Hardware Design: Optimization of sorting circuits in FPGA and ASIC
2. Parallel Algorithms: Sorting implementations on GPU and multi-core processors
3. Cryptography: Oblivious sorting protocols in secure multi-party computation
4. Theoretical Research: Foundation for constructing larger-scale networks

References

The paper cites core literature in the field, including:

• Knuth's classic textbook "The Art of Computer Programming" Volume 3
• Original papers on AKS networks
• Recent SAT solving optimization techniques CCFE+19
• Prefix pruning methods by Bundala and Závodnỳ BZ14

Overall Assessment: This is a high-quality paper achieving substantial progress in sorting network optimization. Although the improvement appears modest (from 14 to 13 layers), in this mature field any improvement is highly valuable. The paper demonstrates strong technical innovation and practicality, providing valuable methods and tools for further development in this area.