Zig-zag sort
From MaRDI portal
Publication:5259604
Abstract: We describe and analyze Zig-zag Sort--a deterministic data-oblivious sorting algorithm running in O(n log n) time that is arguably simpler than previously known algorithms with similar properties, which are based on the AKS sorting network. Because it is data-oblivious and deterministic, Zig-zag Sort can be implemented as a simple O(n log n)-size sorting network, thereby providing a solution to an open problem posed by Incerpi and Sedgewick in 1985. In addition, Zig-zag Sort is a variant of Shellsort, and is, in fact, the first deterministic Shellsort variant running in O(n log n) time. The existence of such an algorithm was posed as an open problem by Plaxton et al. in 1992 and also by Sedgewick in 1996. More relevant for today, however, is the fact that the existence of a simple data-oblivious deterministic sorting algorithm running in O(n log n) time simplifies the inner-loop computation in several proposed oblivious-RAM simulation methods (which utilize AKS sorting networks), and this, in turn, implies simplified mechanisms for privacy-preserving data outsourcing in several cloud computing applications. We provide both constructive and non-constructive implementations of Zig-zag Sort, based on the existence of a circuit known as an epsilon-halver, such that the constant factors in our constructive implementations are orders of magnitude smaller than those for constructive variants of the AKS sorting network, which are also based on the use of epsilon-halvers.
Recommendations
- Deterministic sorting in O(nloglogn) time and linear space
- Randomized shellsort: a simple data-oblivious sorting algorithm
- Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations
- Randomized Shellsort, a simple oblivious sorting algorithm
- Deterministic sorting in nearly logarithmic time on the hypercube and related computers
- The 1.375 approximation algorithm for sorting by transpositions can run in \(O(n\log n)\) time
- A unified \(O(\log N)\) and optimal sorting vector algorithm
- Asymptotically fastest sorting algorithm for almost sorted arrays
- A simpler and faster 1.5-approximation algorithm for sorting by transpositions
Cites work
- scientific article; zbMATH DE number 5485440 (Why is no real title available?)
- scientific article; zbMATH DE number 5485574 (Why is no real title available?)
- Advances in Cryptology – CRYPTO 2004
- Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
- Bounds on the sample complexity for private learning and private data release
- Characterizing the sample complexity of private learners
- Collusion-secure fingerprinting for digital data
- Differential privacy and the fat-shattering dimension of linear queries
- Efficient algorithms for privately releasing marginals via convex relaxations
- Faster algorithms for privately releasing marginals
- Faster private release of marginals on small databases
- Interactive privacy via the median mechanism
- Iterative Constructions and Private Data Release
- Lower bounds in differential privacy
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- On the complexity of differentially private data release, efficient algorithms and hardness results
- On the geometry of differential privacy
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Theory of Cryptography
Cited in
(20)- OptORAMa: optimal oblivious RAM
- Fragile complexity of comparison-based algorithms
- Is there an oblivious RAM lower bound for online reads?
- OptORAMa: Optimal oblivious RAM
- Practically efficient secure single-commodity multi-market auctions
- Cache-oblivious and data-oblivious sorting and applications
- Is there an oblivious RAM lower bound for online reads?
- Multi-client Oblivious RAM Secure Against Malicious Servers
- Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons
- Locality-preserving oblivious RAM
- Fragile complexity of adaptive algorithms
- Laconic function evaluation and ABE for RAMs from (Ring-)LWE
- scientific article; zbMATH DE number 7650132 (Why is no real title available?)
- Randomized shellsort: a simple data-oblivious sorting algorithm
- Randomized Shellsort, a simple oblivious sorting algorithm
- Combinatorial search in two and more rounds
- CacheShuffle: a family of oblivious shuffles
- Can we overcome the \(n\log n\) barrier for oblivious sorting?
- Sorting Short Keys in Circuits of Size ${o(n \log n)}$
- Fragile complexity of adaptive algorithms
This page was built for publication: Zig-zag sort
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259604)
