Lower bounds for sorting networks

Nabil Kahalé, Tom Leighton, Yuan Ma, C. Greg Plaxton, Torsten Suel, Endre Szemerédi

Type: Article

Publication Date: 1995-01-01

Citations: 8

DOI: https://doi.org/10.1145/225058.225178

Similar Works

Action	Title	Year	Authors
+	Lower bounds for sorting of sums	1989	Martin Dietzfelbinger
+ PDF Chat	New Bounds on Optimal Sorting Networks	2015	Thorsten Ehlers Mike Müller
+	Sorting Networks For Large N	2011	Sherenaz W. Al-Haj Baddar Kenneth E. Batcher
+	Optimal-depth sorting networks	2016	Daniel Bundala Michael Codish Luís Cruz-Filipe Peter Schneider–Kamp Jakub Závodný
+	Sorting Algorithms	2017	Marian Mureşan
+ PDF Chat	Optimal Sorting Networks	2014	Daniel Bundala Jakub Závodný
+	A Superlogarithmic Lower Bound for Shuffle-Unshuffle Sorting Networks	2000	C. Gregory Plaxton Torsten Suel
+	Sorting networks	1993	Frederick Hegeman
+ PDF Chat	An Upper Bound for Sorting $$R_n$$ with LRE	2021	Sai Satwik Kuppili Bhadrachalam Chitturi Venkata Vyshnavi Ravella Chhanda Datta
+	Size bounds and parallel algorithms for networks	1980	G. Lev
+	Routing Via Matchings And Optimal Sorting Network On Graphs	2016	Indranil Banerjee Dana Richards
+	Lower bounds to randomized algorithms for graph properties	1991	Andrew Chi-Chih Yao
+	Joint Size and Depth Optimization of Sorting Networks	2018	José A. R. Fonollosa
+	Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey)	2007	Paul Vitányi
+	Lower bounds for arithmetic networks	1993	Jos� L. Monta�a Luis Miguel Pardo
+	Joint Size and Depth Optimization of Sorting Networks.	2018	José Adrián Rodríguez Fonollosa
+ PDF Chat	Fast Combinatorial Algorithms for Efficient Sortation	2024	Madison Van Dyk Kim Klause Jochen Koenemann Nicole Megow
+	Algorithms for Approximation	2006	Armin Iske Jeremy Levesley
+	Algorithms for approximation	1987
+	Algorithms for approximation	1986	E. W. Cheney

Works That Cite This (4)

Action	Title	Year	Authors
+	On Probabilistic Networks for Selection, Merging, and Sorting	1997	T. Leighton Yuan Ma Torsten Suel
+	On probabilistic networks for selection, merging, and sorting	1995	Tom Leighton Yuan Ma Torsten Suel
+	Arguments for the unsuitability of convolutional neural networks for non-local tasks	2021	Sebastian Stabinger David Peer Antonio Rodrı́guez-Sánchez
+	Arguments for the Unsuitability of Convolutional Neural Networks for Non--Local Tasks	2021	Sebastian Stabinger David Peer Antonio Rodrı́guez-Sánchez

Works Cited by This (4)

Action	Title	Year	Authors
+ PDF Chat	Eigenvalues and expansion of regular graphs	1995	Nabil Kahalé
+ PDF Chat	Lower Bounds on Merging Networks	1976	Andrew Chi-Chih Yao Foong Frances Yao
+	The Complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems, Sorting, and Merging	1979	Lamagna
+ PDF Chat	The asymptotic complexity of merging networks	1992	Peter Bro Miltersen Mike Paterson Jun Tarui