Pseudorandom generators, measure theory, and natural proofs

Kenneth W. Regan; D. Sivakumar; Jin yi Cai

Pseudorandom generators, measure theory, and natural proofs

Kenneth W. Regan
, D. Sivakumar
, Jin yi Cai

Department of Computer Science and Engineering

University at Buffalo

SUNY Buffalo

Research output: Contribution to journal › Conference article › peer-review

29 Scopus citations

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 [25]. We also provide a partial converse of this result.

Original language	English
Pages (from-to)	26-35
Number of pages	10
Journal	Annual Symposium on Foundations of Computer Science - Proceedings
State	Published - 1995
Event	Proceedings of the 1995 IEEE 36th Annual Symposium on Foundations of Computer Science - Milwaukee, WI, USA Duration: Oct 23 1995 → Oct 25 1995

Cite this

@article{4ab033a076434b369b29afe8312c550b,

title = "Pseudorandom generators, measure theory, and natural proofs",

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 [25]. We also provide a partial converse of this result.",

author = "Regan, \{Kenneth W.\} and D. Sivakumar and Cai, \{Jin yi\}",

year = "1995",

language = "English",

pages = "26--35",

journal = "Annual Symposium on Foundations of Computer Science - Proceedings",

issn = "0272-5428",

publisher = "IEEE Computer Society",

note = "Proceedings of the 1995 IEEE 36th Annual Symposium on Foundations of Computer Science ; Conference date: 23-10-1995 Through 25-10-1995",

}

TY - JOUR

T1 - Pseudorandom generators, measure theory, and natural proofs

AU - Regan, Kenneth W.

AU - Sivakumar, D.

AU - Cai, Jin yi

PY - 1995

Y1 - 1995

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 [25]. We also provide a partial converse of this result.

AB - 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 [25]. We also provide a partial converse of this result.

UR - https://www.scopus.com/pages/publications/0029510687

M3 - Conference article

SN - 0272-5428

SP - 26

EP - 35

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - Proceedings of the 1995 IEEE 36th Annual Symposium on Foundations of Computer Science

Y2 - 23 October 1995 through 25 October 1995

ER -

Pseudorandom generators, measure theory, and natural proofs

Abstract

Other files and links

Fingerprint

Cite this