U. Feige
- 1.A.K. Chandra, L. Stockmeyer, and U. Vishkin. Constant depth reducibility. SlAM Journal on Computing, 13(2):423-439, 1984.Google Scholar
Cross Ref
- 2.H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Math. Stat., 23:493-509, 1952.Google ScholarCross Ref
- 3.J. Hastad, F.T. Leighton, and M. Newman. Reconfiguring a hypercube in the presence of faults. In 19th Annual Symposium on Theory of Computing, pages 274-284, 1987. Google ScholarDigital Library
- 4.W. goeffding. Probability inequalities for sums of bounded random variables. J. Amer. Stat. Assoc., 58:13-30, 1963.Google ScholarCross Ref
- 5.R.M. Karp. Personal communication. Berkeley, 1989.Google Scholar
- 6.C. Kenyon-Mathieu and A.C. Yao. On evaluating boolean functions with unrealiable tests. Unpublished manuscript, Princeton Univ., 1989.Google Scholar
- 7.D.J. Kleitman, A.R. Meyer, R.L. Rivest, J. Spencer, and K. Winldmann. Coping with errors in binary search procedures. Journal of Computer and System Sciences, 20:396-404, 1980.Google ScholarCross Ref
- 8.D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison- Wesley, Reading, Massachusetts, 1973. Google ScholarDigital Library
- 9.M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27:228-234, 1980. Google ScholarDigital Library
- 10.N. Pippenger. On networks of noisy gates. In g6th Annual Symposium on Foundations of Computer Science, pages 30-38, 1985.Google Scholar
- 11.B. Ravikumar, K. Ganesan, and K.B. Lakshmanan. On selecting the largest element in spite of erroneous information. In Automata, Languages, and Programming, Lecture Notes in Computer Science, pages 88-99. Springer-Verlag, 1987. Google ScholarDigital Library
- 12.B. Ravikumar and K.B. Lakshmanan. Coping with known patterns of lies in a search game. Theoretical Computer Science, 33:85-94, 1984.Google ScholarCross Ref
- 13.R. Reischuk. Probabilistic parallel algorithms for sorting and selection. SlAM Journal on Computing, 14(2):396-409, 1985.Google ScholarCross Ref
- 14.M. SaYs and A. Wigderson. Probabilistic Boolean decision trees and the complexity of evaluating game trees. In 27th Annual Symposium on Foundations of Computer Science, pages 29-38, Toronto, Ontario, 1986.Google Scholar
- 15.J.P.M. Schalkwijk. A class of simple and optimal strategies for block coding on the binary symmetric channel with noiseless feedback. 1EEE Trans. Info. Theory, 17(3):283-283, 1971.Google ScholarDigital Library
- 16.A.C. Yao and F.F. Yao. On fault-tolerant networks for sorting. SlAM Journal on Computing, 14:120- 128, 1985.Google ScholarCross Ref
Index Terms
- Computing with unreliable information
Recommendations
Opportunistic Flooding in Low-Duty-Cycle Wireless Sensor Networks with Unreliable Links
Flooding service has been investigated extensively in wireless networks to efficiently disseminate network-wide commands, configurations, and code binaries. However, little work has been done on low-duty-cycle wireless sensor networks in which nodes ...
Comments