Pseudorandom generators, measure theory, and natural proofs Export

@inproceedings{rsc95, abstract = {We prove that if strong pseudorandom number generators exist, then the class of languages that have polynomial-sized circuits (P/poly) is not measurable within exponential time, in terms of the resource-bounded measure theory of Lutz. We prove our result by showing that if P/poly has measure zero in exponential time, then there is a natural proof against P/poly, in the terminology of Razborov and Rudich (1994). We also provide a partial converse of this result.}, author = {Regan, K. and Sivakumar, D. and Cai, J-}, booktitle = {Foundations of Computer Science, 36th Annual Symposium on}, citeulike-article-id = {112865}, citeulike-linkout-0 = {http://csdl.computer.org/comp/proceedings/focs/1995/7183/00/71830026abs.htm}, keywords = {algorithms, complexitytheory, extractors, probability, pseudorandomness, tcs}, organization = {IEEE}, posted-at = {2005-03-03 09:31:31}, priority = {2}, title = {Pseudorandom generators, measure theory, and natural proofs}, url = {http://csdl.computer.org/comp/proceedings/focs/1995/7183/00/71830026abs.htm}, year = {1995} }

TY - CONF ID - rsc95 L3 - citeulike-article-id:112865 N2 - We prove that if strong pseudorandom number generators exist, then the class of languages that have polynomial-sized circuits (P/poly) is not measurable within exponential time, in terms of the resource-bounded measure theory of Lutz. We prove our result by showing that if P/poly has measure zero in exponential time, then there is a natural proof against P/poly, in the terminology of Razborov and Rudich (1994). We also provide a partial converse of this result. OR - IEEE TI - Pseudorandom generators, measure theory, and natural proofs T2 - Foundations of Computer Science, 36th Annual Symposium on KW - algorithms KW - complexitytheory KW - extractors KW - probability KW - pseudorandomness KW - tcs AU - Regan, K AU - Sivakumar, D AU - Cai, J- PY - 1995/// UR - http://csdl.computer.org/comp/proceedings/focs/1995/7183/00/71830026abs.htm ER -