The strongest model of computation obeying 0-1 Principles

DOI10.1007/S00224-010-9257-8zbMATH Open1209.68252OpenAlexW1994493843MaRDI QIDQ633766FDOQ633766

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

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

zbMATH Keywords

sorting networksoblivious algorithmscomparator networksmin max networkszero-one principle

Mathematics Subject Classification ID

Searching and sorting (68P10)

Cites Work

• Title not available (Why is that?)
• On Dedekind's Problem: The Number of Monotone Boolean Functions
• Title not available (Why is that?)
• K-way bitonic sort
• 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)