Halvers and Expanders

The authors investigate the asymptotic efficiency of certain combinatorial networks called halvers, which are basic building blocks of many parallel algorithms. They improve the efficiency of halvers in terms of their depth. The novelty is the use of combinatorial circuits whose basic units are k-sorter switches. >

Authors

• Miklós Ajtai
• János Komlós
• Endre Szemerédi

Keywords

• Switches
• Sorting
• Parallel algorithms
• Switching circuits
• Registers
• Bipartite graph
• Delay effects
• Binary trees
• Upper Bound
• Set Of Equations
• Work Place
• Perfect Match
• Input Matrix
• Hypergeometric Distribution
• Part Of Matrix
• Organization Of The Paper
• Accuracy Of Network
• Network Depth
• Random Graph
• Output Matrix
• Circuit Elements
• Number Of Matrices
• Jensen’s Inequality
• Parallel Algorithm
• List Size
• Switching Sequence