Sorting Short Keys in Circuits of Size ${o(n \log n)}$
From MaRDI portal
Publication:5080485
DOI10.1137/20M1380983OpenAlexW3140559833WikidataQ114846589 ScholiaQ114846589MaRDI QIDQ5080485
Gilad Asharov, Elaine Shi, Wei-Kai Lin
Publication date: 31 May 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2010.09884
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved sorting networks with O(log N) depth
- Upper bounds for sorting integers on random access machines
- Sorting networks of logarithmic depth, further simplified
- Sorting in \(c \log n\) parallel steps
- Expanders that beat the eigenvalue bound: Explicit construction and applications
- Sorting in linear time?
- On probabilistic networks for selection, merging, and sorting
- Time bounds for selection
- Self-routing superconcentrators
- OptORAMa: optimal oblivious RAM
- Fast parallel space allocation, estimation, and integer sorting
- Is There an Oblivious RAM Lower Bound?
- Data-Oblivious Data Structures
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Bounds on Selection Networks
- Parallelism in Comparison Problems
- Sorting on a parallel pointer machine with applications to set expression evaluation
- Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations
- Network coding in undirected graphs is either very helpful or not helpful at all
- Deterministic sorting in O(nloglogn) time and linear space
- On-Line Algorithms for Path Selection in a Nonblocking Network
- Optimal parallel selection
- Lower bounds for external memory integer sorting via network coding
- Can We Overcome the n log n Barrier for Oblivious Sorting?
- Zig-zag sort
- On the capacity of information networks
This page was built for publication: Sorting Short Keys in Circuits of Size ${o(n \log n)}$
