Zig-zag sort

DOI10.1145/2591796.2591830zbMATH Open1315.68114arXiv1403.2777OpenAlexW2123139266WikidataQ56337891 ScholiaQ56337891MaRDI QIDQ5259604FDOQ5259604

Michael T. Goodrich

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1403.2777

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of Cryptography
• The geometry of differential privacy: the small database and approximate cases
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• On the complexity of differentially private data release
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Characterizing the sample complexity of private learners
• Faster Algorithms for Privately Releasing Marginals
• Faster private release of marginals on small databases
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately releasing conjunctions and the statistical query barrier
• Efficient algorithms for privately releasing marginals via convex relaxations

Cited In (15)

• OptORAMa: optimal oblivious RAM
• Fragile complexity of comparison-based algorithms
• Is there an oblivious RAM lower bound for online reads?
• OptORAMa: Optimal oblivious RAM
• Is there an oblivious RAM lower bound for online reads?
• Multi-client Oblivious RAM Secure Against Malicious Servers
• Title not available (Why is that?)
• Locality-preserving oblivious RAM
• Fragile complexity of adaptive algorithms
• Laconic function evaluation and ABE for RAMs from (Ring-)LWE
• Title not available (Why is that?)
• Practically Efficient Secure Single-Commodity Multi-market Auctions
• Combinatorial search in two and more rounds
• Fragile complexity of adaptive algorithms
• Sorting Short Keys in Circuits of Size ${o(n \log n)}$

Uses Software

• SuLQ

Recommendations

• Deterministic sorting in O(nloglogn) time and linear space 👍 👎
• The 1.375 Approximation Algorithm for Sorting by Transpositions Can Run in O(nlogn) Time 👍 👎
• Randomized Shellsort 👍 👎
• Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations 👍 👎
• A simpler and faster 1.5-approximation algorithm for sorting by transpositions 👍 👎
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers 👍 👎
• A unified \(O(\log N)\) and optimal sorting vector algorithm 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)