Selected papers that cite this one
- Amir M. Ben-Amram. When can we sort in o(n log n) time? Journal of Computer and System Sciences, 54(2):345-370, April 1997.
Selected references
- Michael Ben-Or. Lower bounds for algebraic computation trees (preliminary report). In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 80-86, Boston, Massachusetts, 25-27 April 1983.
- Nathan Friedman. Some results on the effect of arithmetics on comparison problems. In 13th Annual Symposium on Switching and Automata Theory, pages 139-143, The University of Maryland, 25-27 October 1972. IEEE.
- Friedhelm Meyer auf der Heide. Lower bounds for solving linear Diophantine equations on random access machines. Journal of the ACM, 32(4):929-937, October 1985.
- Michael Kaminski and Nader H. Bshouty. Multiplicative complexity of polynomial multiplication over finite fields (extended abstract). In 28th Annual Symposium on Foundations of Computer Science, pages 138-140, Los Angeles, California, 12-14 October 1987. IEEE.
- Yishay Mansour, Baruch Schieber, and Prasoon Tiwari. Lower bounds for integer greatest common divisor computations (extended summary). In 29th Annual Symposium on Foundations of Computer Science, pages 54-63, White Plains, New York, 24-26 October 1988. IEEE.
- Shlomo Moran, Marc Snir, and Udi Manber. Applications of Ramsey's theorem to decision tree complexity. Journal of the ACM, 32(4):938-949, October 1985.
- J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701-717, October 1980.
- Andrew Chi-Chih Yao. Lower bounds for algebraic computation trees with integer inputs. In 30th Annual Symposium on Foundations of Computer Science, pages 308-313, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.