Efficiency considerations in using semi-random sources

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficiency considerations in using semi-random sources

Full text

Pdf (581 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the nineteenth annual ACM symposium on Theory of computing table of contents

New York, New York, United States

Pages: 160 - 168

Year of Publication: 1987

ISBN:0-89791-221-7

Author

U. Vazirani

Harvard University, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 11, Citation Count: 10

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/28395.28413 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Al	N. Alon, 'On VV-s result SRP = RP," unpublished manuscript, May 1985.
	Bl	M. Blum, "Independent Unbiased Coin Flips From a Correlated Biased Source: a Finite State Markov Chain," 25th. IEEE Symposium on the Foundations of Computer Science, 1984.
	CG	B. Chor and O. Goldreich, "Unbiased Bits from Weak Sources of Randomness," 26th. IEEE Symposium on the Foundations of Computer Science, 1985.
	El	P. Elias, "The Efficient Construction of an Unbiased Random Sequence," Ann. Math. Statist. Vol 43, No. 3, 1972, 865-870.
	Ga	Robert G. Gallager, Information Theory and Reliable Communication, John Wiley & Sons, Inc., New York, NY, 1968
	Ho	C. Hooley, 'iDn Artin's Conjecture," CreUe's Journal, 225, (1967), pp 209-220.
	Ju	J. Justesen, "A Class of Constructive Asymptotically Good Algebraic Codes,*' IEEE Trans. Inform. Theory, vol IT-18, pp 652-656, Sept
	vN	J. yon Neumann, "Various Techniques Used in Connection with Random Digits," Notes by G. E. For sythe, National Bureau of' Standards, Applied Math Series, 1951, Vol 12, 36-38. Reprinted in yon Neumann's Collected Works, Vol 5, Pergamon Press (1963), 768- 770.
	SV	Miklos Santha , Umesh V Vazirani, Generating quasi-random sequences from semi-random sources, Journal of Computer and System Sciences, v.33 n.1, p.75-87, Aug. 1986 [doi>10.1016/0022-0000(86)90044-9]
	Sh	Daniel Shanks, Solved and unsolved problems in number theory, Chelsea Publishing Co., Inc., New York, 1985
	Va	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, p.366-378, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22186]
	Va2	Umesh Virkumar Vazirani, Randomness, adversaries and computation (random polynomial time), 1986
	VV1	U.V. Vazirani and V. V. Vazirani, "'Random Polynomial Time is Equal to Semi-Random Polynomial Time," 26th. {EEE Symposium on the Foundations of Computer Science, 1985.
	VV2	U V Vazirani , V V Vazirani, Sampling a population with a semi-random source, Proc. of the sixth conference on Foundations of software technology and theoretical computer science, p.443-452, December 1986, New Delhi, India
	Wy	A. Wyner, '~Wire-tap Channel," Bell System Technical Journal, pp 1355-1387, Oct. 1975.
	Ya2	A. Yao, 'ff'heory and Applications of Trapdoor Functions," 23th. IEEE Symposium on the Foundations of Computer Science, 1982.

CITED BY 10

	Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Nathan Linial , Steven Phillips, Biased random walks, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.1-9, May 04-06, 1992, Victoria, British Columbia, Canada
	O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States
	Michael Saks , Aravind Srinivasan , Shiyu Zhou, Explicit dispersers with polylog degree, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.479-488, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Ran Raz , Omer Reingold , Salil Vadhan, Extracting all the randomness and reducing the error in Trevisan's extractors, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.149-158, May 01-04, 1999, Atlanta, Georgia, United States
	B. Vallée, Provably fast integer factoring with quasi-uniform small quadratic residues, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.98-106, May 14-17, 1989, Seattle, Washington, United States
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	William Aiello , Sivaramakrishnan Rajagopalan , Ramarathnam Venkatesan, Design of practical and provably good random number generators, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.1-9, January 22-24, 1995, San Francisco, California, United States
	N. Nisan, Pseudorandom generators for space-bounded computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.204-212, May 13-17, 1990, Baltimore, Maryland, United States
	Ran Raz , Omer Reingold , Salil Vadhan, Extracting all the randomness and reducing the error in Trevisan's extractors, Journal of Computer and System Sciences, v.65 n.1, p.97-128, August 2002
	Ran Raz, Extractors with weak random seeds, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA