{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T18:51:24Z","timestamp":1771872684202,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1987,12,1]],"date-time":"1987-12-01T00:00:00Z","timestamp":565315200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1987,12]]},"DOI":"10.1007\/bf02579325","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T22:20:05Z","timestamp":1174602005000},"page":"375-392","source":"Crossref","is-referenced-by-count":70,"title":["Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources"],"prefix":"10.1007","volume":"7","author":[{"given":"Umesh V.","family":"Vazirani","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02579325_CR1","unstructured":"N. Alon, On VV-s result SRP=RP, unpublished manuscript, 1985."},{"key":"BF02579325_CR2","doi-asserted-by":"crossref","unstructured":"A. Aho, J. Ullman andM. Yannakakis, On Notions of Information Transfer in VLSI Circuits,15th Annual Symp. on Theory of Computing, (1983), 133\u2013139.","DOI":"10.1145\/800061.808742"},{"key":"BF02579325_CR3","doi-asserted-by":"crossref","unstructured":"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).","DOI":"10.1109\/SFCS.1984.715944"},{"key":"BF02579325_CR4","unstructured":"B. Chor andO. Goldreich, Unbiased Bits from Weak Sources of Randomness,26th IEEE Symposium on the Foundations of Computer Science (1985)."},{"key":"BF02579325_CR5","volume-title":"Information Theory and Reliable Communication","author":"R. Gallager","year":"1986","unstructured":"R. Gallager,Information Theory and Reliable Communication, New York: John Wiley, (1986)."},{"key":"BF02579325_CR6","doi-asserted-by":"crossref","unstructured":"B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich andR. Smolensky, The Bit Extraction Problem ort-Resilient Functions,26th IEEE Symposium on the Foundations of Computer Science, (1985).","DOI":"10.1109\/SFCS.1985.55"},{"key":"BF02579325_CR7","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1214\/aoms\/1177692552","volume":"43","author":"P. Elias","year":"1972","unstructured":"P. Elias, The efficient Construction of an Unbiased Random Sequence,Ann. Math. Statist. 43 (1972), 865\u2013870.","journal-title":"Ann. Math. Statist."},{"key":"BF02579325_CR8","unstructured":"El-Gamal andOrlitzky, Randomized Communication Complexity, preprint."},{"key":"BF02579325_CR9","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1109\/TIT.1972.1054893","volume":"18","author":"J. Justesen","year":"1972","unstructured":"J. Justesen, A class of Constructive Asymptotically Good Algebraic Codes,IEEE Trans. Inform. Theory,18 (1972), 652\u2013656.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"BF02579325_CR10","doi-asserted-by":"crossref","unstructured":"R. Lipton andR. Sedgewick, Lower bounds for VLSI,Proc. 13th Ann. ACM Symp. on Theory of Computing, (1981), 300\u2013307.","DOI":"10.1145\/800076.802482"},{"key":"BF02579325_CR11","doi-asserted-by":"crossref","unstructured":"K. Melhorn andE. Schmidt, Las Vegas is better than Determinism in VLSI and Distributed Computing,14th Annual Symp. on Theory of Computing, (1982), 330\u2013337.","DOI":"10.1145\/800070.802208"},{"key":"BF02579325_CR12","first-page":"36","volume":"12","author":"J. Neumann von","year":"1951","unstructured":"J. von Neumann, Various Techniques Used in Connection with Random Digits, Notes by G. E. Forsythe, National Bureau of Standards,Applied Math. Series,12, (1951), 36\u201338. Reprinted in von Neumann\u2019s Collected Works, Vol 5, Pergamon Press (1963), 768\u2013770.","journal-title":"Applied Math. Series"},{"key":"BF02579325_CR13","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou andM. Sipser, Communication complexity,Proc. 14th Ann. ACM Symp. on Theory of Computing, (1982), 196\u2013200.","DOI":"10.1145\/800070.802192"},{"key":"BF02579325_CR14","doi-asserted-by":"crossref","unstructured":"P. Raghavan, Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs,27th. IEEE Symposium on the Foundations of Computing, (1986).","DOI":"10.1109\/SFCS.1986.45"},{"key":"BF02579325_CR15","unstructured":"W. Rudin,Principles of Mathematical Analysis, Third Edition, McGraw-Hill Book Company."},{"key":"BF02579325_CR16","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0022-0000(86)90044-9","volume":"33","author":"M. S\u00e1ntha","year":"1986","unstructured":"M. S\u00e1ntha andU. V. Vazirani, Generating Quasi-random Sequences from Semi-random Sources,Journal of Computer Systems and Sciences,33, (1986), 75\u201387.","journal-title":"Journal of Computer Systems and Sciences"},{"key":"BF02579325_CR17","doi-asserted-by":"crossref","unstructured":"C. Thompson, Area-Time Complexity for VLSI,11th Annual Symp. on Theory of Computing, (1979), 81\u201388. to appear in JCSS (currently, Proc. STOC 1985).","DOI":"10.1145\/800135.804401"},{"key":"BF02579325_CR18","unstructured":"U. V. Vazirani, Randomness, Adversaries and Computation,Ph. D. Dissertation, U. C. Berkeley, (1986)."},{"key":"BF02579325_CR19","doi-asserted-by":"crossref","unstructured":"U. V. Vazirani andV. V. Vazirani, Trapdoor Pseudo-random Number Generators with Applications to Protocol Design,15th Annual ACM Symp. on Theory of Computing, (1983).","DOI":"10.1109\/SFCS.1983.78"},{"key":"BF02579325_CR20","doi-asserted-by":"crossref","unstructured":"U. V. Vazirani andV. V. Vazirani, Random Polynomial Time is Equal to Semi-Random Polynomial Time,26th. IEEE Symposium on the Foundations of Computer Science, (1985).","DOI":"10.1109\/SFCS.1985.45"},{"key":"BF02579325_CR21","doi-asserted-by":"crossref","unstructured":"U. V. Vazirani andV. V. Vazirani, Sampling a Population with a Semirandom source,Proceedings Sixth Ann. FST-TCS Conference, New Delhi, (1986).","DOI":"10.1007\/3-540-17179-7_27"},{"key":"BF02579325_CR22","doi-asserted-by":"crossref","unstructured":"A. Wyner, Wire-tap Channel,Bell System Technical Journal, (1975).","DOI":"10.1002\/j.1538-7305.1975.tb02040.x"},{"key":"BF02579325_CR23","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Some Complexity Questions related to Distributive computing,Proc. 11th Ann. ACM Symp on the Theory of Computing, (1979), 209\u2013213.","DOI":"10.1145\/800135.804414"},{"key":"BF02579325_CR24","doi-asserted-by":"crossref","unstructured":"A. Yao, Theory and Applications of Trapdoor Functions,23th IEEE Symposium on the Foundations of Computer Science, (1982).","DOI":"10.1109\/SFCS.1982.45"},{"key":"BF02579325_CR25","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Lower Bounds by Probabilistic Arguments,Proc. 24 Ann. Symp on the Theory of Computing, (1983), 420\u2013428.","DOI":"10.1109\/SFCS.1983.30"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579325.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579325\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579325","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T16:45:02Z","timestamp":1558197902000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579325"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,12]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1987,12]]}},"alternative-id":["BF02579325"],"URL":"https:\/\/doi.org\/10.1007\/bf02579325","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,12]]}}}