Rounds vs. Queries Tradeoff in Noisy Computation

by Navin Goyal and Michael Saks

Theory of Computing, Volume 6(6), pp. 113-134, 2010

Bibliography with links to cited articles

[1]   Miklós Ajtai, János Komlós, W. L. Steiger, and Endre Szemerédi: Optimal parallel selection has complexity O(log log n). J. Comput. System Sci., 38(1):125–133, 1989. [doi:10.1016/0022-0000(89)90035-4].

[2]   William Evans and Nicholas Pippenger: Average-case lower bounds for noisy Boolean decision trees. SIAM J. Comput., 28(2):433–446, 1998. [doi:10.1137/S0097539796310102].

[3]   Uriel Feige: On the complexity of finite random functions. Inform. Process. Lett., 44(6):295–296, 1992. [doi:10.1016/0020-0190(92)90102-2].

[4]   Uriel Feige and Joe Kilian: Finding OR in a noisy broadcast network. Inform. Process. Lett., 73(1-2):69–75, 2000. [doi:10.1016/S0020-0190(00)00002-8].

[5]   Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal: Computing with noisy information. SIAM J. Comput., 23(5):1001–1018, 1994. [doi:10.1137/S0097539791195877].

[6]   Eyal Kushilevitz and Yishay Mansour: Computation in noisy radio networks. SIAM J. Discrete Math., 19(1):96–108, 2005. [doi:10.1137/S0895480103434063].

[7]   Ilan Newman: Computing in fault tolerance broadcast networks. In Proc. IEEE Conf. on Comput. Complex., pp. 113–122. IEEE Comp. Soc. Press, 2004. [doi:10.1109/CCC.2004.1313813].

[8]   Rüdiger Reischuk: Probabilistic parallel algorithms for sorting and selection. SIAM J. Comput., 14(2):396–409, 1985. [doi:10.1137/0214030].

[9]   Rüdiger Reischuk and Bernd Schmeltz: Reliable computation with noisy circuits and decision trees—A general nlog n lower bound. In Proc. 32nd FOCS, pp. 602–611. IEEE Comp. Soc. Press, 1991. [doi:10.1109/SFCS.1991.185425].

[10]   Yossi Shiloach and Uzi Vishkin: Finding the maximum, merging, and sorting in a parallel computation model. J. Algorithms, 2(1):88–102, 1981.

[11]   Leslie G. Valiant: Parallelism in comparison problems. SIAM J. Comput., 4(3):348–355, 1975. [doi:10.1137/0204030].

[12]   John von Neumann: Various techniques used in connection with random digits. In A. S. Householder, G. E. Forsythe, and H. H. Germond, editors, Monte Carlo Method, volume 12 of National Bureau of Standards Applied Mathematics Series, pp. 36–38. 1951.

[13]   Andrew Chi-Chih Yao: Probabilistic computations: Toward a unified measure of complexity. In Proc. 18th FOCS, pp. 222–227. IEEE Comp. Soc. Press, 1977. [doi:10.1109/SFCS.1977.24].