David E. Muller
- 1 LEVY, S Y , AND PAVLL, M C. An algebra with applicatmn to sorting algorithms. Proc. Third Princeton Conference on Information Sciences and Systems, Pnnceton U, Princeton, N J, March 1969, pp. 286-291Google Scholar
- 2 BATCHER, K. E Sorting networks and their applications. Proc. AFIPS 1968 SJCC, Vol. 32, AFIPS Press, Montvale, N J, pp. 307-313Google Scholar
- 3 KNUTH, D E. The Art of Computer Programming, Vol 1II Addison-Wesley, Reading, Mass, 1973, Ch. 5 Google Scholar
- 4 GREEN, M W Some improvements in nonadaptive sorting algorithms Proc Sixth Princeton Conference on Information Sciences and Systems, March 1972, pp 387-391.Google Scholar
- 5 :FOSTER, C. C, AND STOCKTON, :F. D Counting responders in an associative memory 1EEE Trans Comput C-ZO, 12 (Dec. 1971), 1580--1583.Google Scholar
- 6 MEYER, A R, FISCHER, M. J, AND VILFAN, B The length of formula representations of Boolean functions. Dep Elec Eng., M I T, Cambridge, Mass, 1971 (unpublished manuscript)Google Scholar
Index Terms
- Bounds to Complexities of Networks for Sorting and for Switching
Recommendations
Rademacher and gaussian complexities: risk bounds and structural results
We investigate the use of certain data-dependent estimates of the complexity of a function class, called Rademacher and Gaussian complexities. In a decision theoretic setting, we prove general risk bounds in terms of these complexities. We consider ...
Tight complexity bounds for parallel comparison sorting
SFCS '86: Proceedings of the 27th Annual Symposium on Foundations of Computer ScienceThe time complexity of sorting n elements using p ≥ n processors on Valiant's parallel comparison tree model is considered. The following results are obtained. 1. We show that this time complexity is Θ(logn/log(1+p/n)). This complements the AKS sorting ...
Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds
We give a general transformation that turns polynomial-size Frege proofs into subexponential-size AC0-Frege proofs. This indicates that proving truly exponential lower bounds for AC0-Frege is hard, as it is a long-standing open problem to prove ...
Comments