Sorting Short Keys in Circuits of Size {o(n \log n)}
From MaRDI portal
Publication:5080485
DOI10.1137/20M1380983OpenAlexW3140559833WikidataQ114846589 ScholiaQ114846589MaRDI QIDQ5080485FDOQ5080485
Authors: Gilad Asharov, Wei-Kai Lin, Elaine Shi 
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
Recommendations
Cites Work
- Title not available (Why is that?)
- Parallelism in Comparison Problems
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Sorting in \(c \log n\) parallel steps
- Deterministic sorting in O(nloglogn) time and linear space
- Time bounds for selection
- Sorting networks of logarithmic depth, further simplified
- Sorting in linear time?
- Improved sorting networks with O(log N) depth
- On the capacity of information networks
- Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations
- Title not available (Why is that?)
- Upper bounds for sorting integers on random access machines
- On-Line Algorithms for Path Selection in a Nonblocking Network
- Optimal parallel selection
- Bounds on Selection Networks
- Expanders that beat the eigenvalue bound: Explicit construction and applications
- Fast parallel space allocation, estimation, and integer sorting
- Sorting on a parallel pointer machine with applications to set expression evaluation
- Can we overcome the \(n\log n\) barrier for oblivious sorting?
- Title not available (Why is that?)
- On probabilistic networks for selection, merging, and sorting
- OptORAMa: optimal oblivious RAM
- Self-routing superconcentrators
- Data-oblivious data structures
- Is there an oblivious RAM lower bound?
- Lower bounds for external memory integer sorting via network coding
- Zig-zag sort
- Title not available (Why is that?)
- Network coding in undirected graphs is either very helpful or not helpful at all
This page was built for publication: Sorting Short Keys in Circuits of Size ${o(n \log n)}$
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080485)
