# A Unified Theory of Pseudorandomness (NSF CCF-0133096)

Why simple hash functions work: Exploiting the entropy in a data stream.” Theory of Computing 9 (2013): 897-945. Publisher's VersionAbstract THEORYCOMP2013.pdf RANDOM2008.pdf SODA2008.pdf

. “The computational complexity of Nash equilibria in concisely represented games.” ACM Transactions on Computation Theory 4, no. 2 (2012). Publisher's VersionAbstract ACM2012.pdf EC2006.pdf ECCC2005.pdf

. “Deterministic extractors for small-space sources.” Journal of Computer and System Sciences 77, no. 1 (2011): 191-220. Publisher's VersionAbstract JCSS2011.pdf STOC-05-2006.pdf

. “S-T connectivity on digraphs with a known stationary distribution.” In ACM Transactions on Algorithms. Vol. 7. 3rd ed. ACM, 2011. Publisher's VersionAbstract ECCC2007.pdf ACM2011.pdf

. “A lower bound on list size for list decoding.” IEEE Transactions on Information Theory 56, no. 11 (2010): 5681-5688. Publisher's VersionAbstract RANDOM2005.pdf

. “Unbalanced expanders and randomness extractors from Parvaresh–Vardy codes.” Journal of the ACM 56, no. 4 (2009): 1–34. Publisher's VersionAbstract JACM2009.pdf CCC2007.pdf ECCC2006.pdf ECCC - Rev. 2008.pdf

. “The hardness of the expected decision depth problem.” Information Processing Letters 101, no. 3 (2007): 112-118. Publisher's VersionAbstract IPL2007.pdf

. “Amplifying collision-resistance: A complexity-theoretic treatment.” In A. Menezes, editor, Advances in Cryptology (CRYPTO '07), 4622:264-283. Lecture Notes in Computer Science, Springer-Verlag, 2007. Publisher's VersionAbstract CRYPTO2007.pdf

. “Robust PCPs of proximity, shorter PCPs, and applications to coding.” SIAM Journal on Computing: Special Issue on Randomness and Complexity 36, no. 4 (2006): 889-974. Publisher's VersionAbstract SICOMP2006.pdf

. “Using nondeterminism to amplify hardness.” SIAM Journal on Computing: Special Issue on STOC '04 35, no. 4 (2006): 903-931. Publisher's VersionAbstract SICOMP2006.pdf

. “An unconditional study of computational zero knowledge.” SIAM Journal on Computing: Special Issue on Randomness and Complexity 36, no. 4 (2006): 1160-1214. Publisher's VersionAbstract SICOMP2006.pdf

. “Pseudorandom walks in regular digraphs and the RL vs. L problem.” In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC ‘06), 457-466, 2006, 457-466. Publisher's VersionAbstract ACM2006.pdf ECCC2005.pdf

. “Zero knowledge with efficient provers.” In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC ‘06), 287-295. ACM, 2006. Publisher's VersionAbstract STOC2006.pdf

. “Random selection with an adversarial majority.” In Advances in Cryptology—CRYPTO ‘06, C. Dwork, ed. 4117:409–426. Springer Verlag, Lecture Notes in Computer Science, 2006. Publisher's VersionAbstract CRYPTO2006.pdf ECCC-02.2006.pdf FULL-06.2006.pdf

. “Compression of samplable sources.” Computational Complexity: Special Issue on CCC'04 14, no. 3 (2005): 186-227. Publisher's VersionAbstract CC2005.pdf

. “Short PCPs verifiable in polylogarithmic time.” In Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC '05), 120-134, 2005, 120-134. Publisher's VersionAbstract

. “Derandomized squaring of graphs.” In Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM '05), 3624:436-447. Berkeley, CA: Springer Verlag, Lecture Notes in Computer Science, 2005. Publisher's VersionAbstract RANDOM2005.pdf

. “