Fragile complexity of adaptive algorithms

DOI10.1016/j.tcs.2022.03.034OpenAlexW4220841793MaRDI QIDQ5918676

Riko Jacob, John Iacono, Prosenjit Bose, Rolf Fagerberg, Stefan Langerman, Pilar Cano

Publication date: 10 May 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

algorithmscomparison based algorithmsfragile complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Improved sorting networks with O(log N) depth
• Constructing sorting networks from k-sorters
• Sorting networks of logarithmic depth, further simplified
• Sorting in \(c \log n\) parallel steps
• Automata, languages and programming. Eighth Colloquium, Acre (Akko), Israel, July 13-17, 1981
• A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time
• Pseudorandomness
• Tight Lower Bounds for the Online Labeling Problem
• The periodic balanced sorting network
• Expander graphs and their applications
• Selection Networks
• Lower Bounds on Merging Networks
• A Method of Constructing Selection Networks with $O(\log n)$ Depth
• Comparator networks for binary heap construction
• Zig-zag sort

This page was built for publication: Fragile complexity of adaptive algorithms