Диссертация (1103424), страница 25
Текст из файла (страница 25)
Trading Group Theory for Randomness / L. Babai //Proceedings of the 17th annual ACM symposium on Theory ofcomputing. 1985. P. 421429.12. Buhrman, H. Resource bounded Kolmogorov complexity revisited /H. Buhrman, L. Fortnow, S. Laplante // SIAM Journal on Computing. 2002. Vol. 31, no. 3. P. 887905.13. Buhrman, H. Language Compression and Pseudorandom Generators /H. Buhrman, T. Lee, D.
van Melkebeek // Computational Complexity. 2005. Vol. 14. P. 247274.14. Chaitin, G.J. On the length of programs for computing binary sequences/ G.J. Chaitin // Journal of the ACM 1966. Vol. 13, no. 4. P.547569.15. Chaitin, G.J. On the length of programs for computing binary sequences:statistical considerations / G.J. Chaitin // Journal of the ACM. 1969. Vol. 16, no. 1. P. 145159.16. Chor, B. Unbiased Bits From Sources of Weak Randomness andProbabilistic Communication / B. Chor, O. Goldreich // SIAM Journalon Computing.
1988. Vol. 17, no. 2. P. 230261.17. Dvir, Z. Kakeya Sets, New Mergers, and Old Extractors / Z. Dvir,A. Wigderson // SIAM Journal of Computing. 2011. Vol. 40, no. 3. P. 778792.18. Fortnow, L. Extracting Kolmogorov Complexity with Applicationsto Dimension Zero-One Laws / L. Fortnow, J. Hitchcock, A. Pavan,N.V. Vinodchandran, F. Wang // Information and Computation. 2011. Vol. 209, no. 4. P. 627636.12319. Furst, M.
Parity, Circuits, and the Polynomial-Time Hierarchy /M. Furst, J.B. Saxe, M. Sipser // Mathematical systems theory. 1984. Vol. 17, no. 1. P. 1327.20. Goldreich, O. Three XOR-Lemmas an Exposition / O. Goldreich// Studies in Complexity and Cryptography. 2011. Springer LNCSVol. 6650.
P. 248272.21. Guruswami, V. Unbalanced Expanders and Randomness Extractorsfrom Parvaresh-Vardy Codes / V. Guruswami, C. Umans, S. Vadhan //Journal of the ACM. 2009. Vol. 56, no. 4. P. 20:120:34.22. Hitchcock, J. Kolmogorov Complexity in Randomness Extraction /J.M. Hitchcock, A. Pavan, N.V. Vinodchandran // ACM Transactions onComputation Theory. 2011. Vol. 3, no.
1. P. 1:11:??.23. Hoeding, W. Probability Inequalities for Sums of Bounded RandomVariables / W. Hoeding // Journal of the American StatisticalAssociation. 1963. Vol. 58, no. 301. P. 1330.24. Impagliazzo, R. Pseudo-Random Generation from One-Way Functions/ R. Impagliazzo, L.A. Levin, M. Luby // Proceedings of the 21st AnnualACM Symposium on the Theory of Computing. 1989. P. 1224.25. Impagliazzo, R.
Hardness as randomness: A survey of universalderandomization / R. Impagliazzo // Proceedings of the ICM. 2002. Vol. 3. P. 659672.26. Kabanets, V. Derandomization: A Brief Overview / V. Kabanets //Current Trends in Theoretical Computer Science: The Challenge of theNew Century, Vol 1: Algorithms and Complexity. World ScienticPublishing Company, 2004. P. 165187.27. Lee, T. Resource-Bounded Symmetry of Information Revisited / T. Lee,A.
Romashchenko // Theoretical Computer Science. 2005. Vol. 345,no. 23. P. 386405.28. Li, M. An Introduction to Kolmogorov Complexity and its Applications/ M. Li, P.M.B. Vitanyi. 3rd Edition. Springer, 2008. XXIV, 792p.12429. Lu, C.-J. Extractors: Optimal up to Constant Factors / C.-J. Lu, O.Reingold, S.
Vadhan, A. Wigderson // Proceedings of the 35th AnnualACM Symposium on the Theory of Computing. 2003. P. 602611.30. Muchnik, An.A. Conditional Complexity and Codes / An.A. Muchnik //Theoretical Computer Science. 2002. Vol. 271, no. 12. P. 97109.31. Naor, J. Small-Bias Probability Spaces: Ecient Constructions andApplications / J. Naor, M. Naor // SIAM Journal of Computing. 1993. Vol. 22, no. 4. P. 838856.32. Nisan, N. Pseudorandom Bits for Constant Depth Circuits / N.
Nisan //Combinatorica. 1991. Vol. 11, no. 1. P. 6370.33. Nisan, N. Extracting Randomness: A Survey and New Constructions /N. Nisan, A. Ta-Shma // Journal of Computer and System Sciences. 1999. Vol. 58, no. 1. P. 148173.34. Nisan, N. Hardness vs. Randomness. / N. Nisan, A. Wigderson // Journalof Computer and System Sciences. 1994. Vol. 49. P. 149167.35. Nisan, N. Randomness is Linear in Space / N. Nisan, D.
Zuckerman //Journal of Computer and System Sciences. 1996. Vol. 52, no. 1. P. 4352.36. Radhakrishnan, J. Bounds for Dispersers, Extractors, and Depth-TwoSuperconcentrators / J. Radhakrishnan, A. Ta-Shma // SIAM Journal onDiscrete Mathematics. 2000.
Vol. 13, no. 1. P. 224.37. Raz, R. Extracting All the Randomness and Reducing the Error inTrevisan's Extractor / R. Raz, O. Reingold, S. Vadhan // Proceedingsof the 30th Annual ACM Symposium on the Theory of Computing. 1999. P. 149158.38. Reingold, O. Extracting Randomness via Repeated Condensing /O. Reingold, R. Shaltiel, A. Wigderson // SIAM Journal on Computing. 2006. Vol.
35, no. 5. P. 11851209.39. Romashchenko, A.E. Pseudo-Random Graphs and Bit Probe Schemeswith One-Sided Error / A.E. Romashchenko // Theory of ComputingSystems. 2014. Vol. 55, no. 2. P. 313329.12540. Shaltiel, R. Recent Developments in Explicit Constructions of Extractors/ R. Shaltiel // Current and Trends in Theoretical Computer Science: TheChallenge of the New Century. Volume 1: Algorithms and Complexity. World Scientic, 2002. P.
189228.41. Shaltiel, R. An Introduction to Randomness Extractors / R. Shaltiel //Proceedings of the International Conference on Automata, Languages andProgramming. 2011. LNCS Vol. 6756, no. 2. P. 2141.42. Shen, A. Combinatorial Proof of Muchnik's Theorem / A. Shen //Kolmogorov complexity and applications / M. Hutter, W.
Merkle,P. Vitanyi, eds. 2006. Dagstuhl Seminar Proceedings 06051. http://drops.dagstuhl.de/opus/volltexte/2006/625.43. Sipser, M. A Complexity Theoretic Approach to Randomness / M. Sipser// Proceedings of the 15th Annual ACM Symposium on Theory ofComputing. 1983. P. 330335.44. Slepian, D. Noiseless Coding of Correlated Information Sources /D. Slepian, J. K. Wolf // IEEE Transactions on Information Theory. 1973. Vol. 19. P. 471480.45.
Solomono, R.J. A Formal Theory of Inductive Inference, Part 1, Part 2/ R.J. Solomono // Information and Control (now Infromation andComputation). 1964. Vol. 7. P. 122, 224254.46. Srinivasan, A. Computing with Very Weak Random Sources /A. Srinivasan, D. Zuckerman // SIAM Journal on Computing. 1999. Vol.
28. P. 14331459.47. Sudan, M. Decoding of Reed-Solomon Codes beyond the ErrorCorrecting Bound / M. Sudan // Journal of Complexity. 1997. Vol.13, no. 1. P.180193.48. Ta-Shma, A. Loss-less condensers, unbalanced expanders, and extractors/ A. Ta-Shma, C. Umans, D. Zuckerman // Proceedings of the 33rd AnnualACM Symposium on the Theory of Computing. 2001. P.
143152.49. Trevisan, L. Construction of Extractors Using Pseudo-RandomGenerators / L. Trevisan // Journal of the ACM. 2001. Vol. 48,no. 4. P. 860879.12650. Vadhan,S. Pseudorandomnesssurvey/monograph. 2012. /S.Vadhan.Drafthttp://people.seas.harvard.edu/ salil/pseudorandomness/51. Vazirani, U.V. Ecient and Secure Pseudo-Random NumberGeneration / U.V. Vazirani, and V.V. Vazirani // Proceedings of the 25thIEEE Symposium on Foundation of Computer Science. 1984. P.
458463.52. Viola, E. Randomness Buys Depth for Approximate Counting / E. Viola// Proceedings of the 52nd IEEE Symposium on Foundation of ComputerScience. 2011. P. 230239.53. Zimand, M. Two Sources are Better than One for Increasing theKolmogorov Complexity of Innite Sequences / M.
Zimand // Proceedingsof the 3rd Computer Science Symposium in Russia. 2008. LNCS,Vol. 5010. P. 326338.54. Zimand, M. Extracting the Kolmogorov Complexity of Strings andSequences from Sources with Limited Independence / M. Zimand //Proceedings the 26th Symposium on Theoretical Aspects of ComputerScience. 2009. P. 697708.55.
Zimand, M. Impossibility of Independence Amplication in KolmogorovComplexity Theory / M. Zimand // Proceedings of the 35th InternationalSymposium on Mathematical Foundations of Computer Science. 2010. LNCS, Vol. 6281. P. 701712.56. Zimand, M. Possibilities and Impossibilities in Kolmogorov ComplexityExtraction / M. Zimand // SIGACT News. 2010. Vol. 41, no. 4. P, 7494.57.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
