The strongest model of computation obeying 0-1 Principles

DOI10.1007/S00224-010-9257-8MaRDI QIDQ633766zbMATH OpenOpenAlexFDO

Authors Tamir Levi, Ami Litman

Publication date 30 March 2011

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.625.5190

zbMATH Keywords

sorting networksoblivious algorithmscomparator networksmin max networkszero-one principle

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• A generalization of the 0-1 principle for sorting
• A generalization of the zero-one principle for sorting algorithms
• Incomparability in parallel computation
• Accelerating certain outputs of merging and sorting networks
• Strongly exponential lower bounds for monotone computation

Cites work

• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1142303 (Why is no real title available?)
• K-way bitonic sort
• On Dedekind's Problem: The Number of Monotone Boolean Functions
• The asymptotic complexity of merging networks

Cited in

(3)

• Bitonic sorters of minimal depth
• On the complexity of min-max sorting networks
• A generalization of the zero-one principle for sorting algorithms

This page was built for publication: The strongest model of computation obeying 0-1 Principles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633766)