Efficiency considerations in using semi-random sources
作者： U. Vazirani
DOI: 10.1145/28395.28413
关键词:
摘要: Randomness is an important computational resource, and has found application in such diverse tasks as combinatorial algorithms, synchronization deadlock resolution protocols, encrypting data cryptographic protocols. Blum [Bl] pointed out the fundamental fact that whereas all these applications of randomness assume a source independent, unbiased bits, available physical sources (such zener diodes) suffer seriously from problems correlation. A general
acm.org
berkeley.edu参考文章(12)
Umesh Virkumar Vazirani, Randomness, adversaries and computation (random polynomial time) University of California, Berkeley. ,(1986)
Umesh V. Vazirani, Vijay V. Vazirani, Sampling a population with a semi-random source foundations of software technology and theoretical computer science. pp. 443- 452 ,(1986) , 10.1007/3-540-17179-7_27
Umesh V. Vazirani, Vijay V. Vazirani, Random Polynomial Time is Equal to Semi-Random Polynomial Time Cornell University. ,(1988)
Miklos Santha, Umesh V. Vazirani, Generating quasi-random sequences from semi-random sources Journal of Computer and System Sciences. ,vol. 33, pp. 75- 87 ,(1986) , 10.1016/0022-0000(86)90044-9
U V Vazirani, Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85. pp. 366- 378 ,(1985) , 10.1145/22145.22186
J. Justesen, Class of constructive asymptotically good algebraic codes IEEE Transactions on Information Theory. ,vol. 18, pp. 652- 656 ,(1972) , 10.1109/TIT.1972.1054893
A. D. Wyner, The Wire-Tap Channel Bell System Technical Journal. ,vol. 54, pp. 1355- 1387 ,(1975) , 10.1002/J.1538-7305.1975.TB02040.X
David R. Shanks, Solved and Unsolved Problems in Number Theory ,(1962)
Benny Chor, Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity 26th Annual Symposium on Foundations of Computer Science (sfcs 1985). pp. 429- 442 ,(1985) , 10.1109/SFCS.1985.62
Robert G. Gallager, Information Theory and Reliable Communication ,(1968)