Name
Abstract | ||
|---|---|---|
In this paper we extend a key result of Nisan and Wigderson (J. Comput. System Sci. 49 (1994) 149-167) to the nondeterministic setting: for all alpha > 0 we show that if there is a language in E = DTIME(2(O(n))) that is hard to approximate by nondeterministic circuits of size 2(alphan), then there is a pseudorandom generator that can be used to derandomize BP (.) NP tin symbols, BP NP = NP). By applying this extension we are able to answer some open questions in Lutz (Theory Comput. Systems 30 (1997) 429-442) regarding the derandomization of the classes BP (.) Sigma (P)(k) and BP (.) Theta (P)(k) under plausible measure theoretic assumptions. As a consequence, if Theta (P)(2) does not have p-measure 0, then AM boolean AND coAM is low for Theta (P)(2) Thus, in this case, the graph isomorphism problem is low for Theta (P)(2). By using the Nisan-Wigderson design of a pseudorandom generator we unconditionally show the inclusion MA subset of or equal to Zpp(NP), and that MA boolean AND coMA is low for Zpp(NP). (C) 2001 Elsevier Science B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1016/S0304-3975(99)00164-4 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
resource-bounded measure | Journal | 255 |
Issue | ISSN | Citations |
1-2 | 0304-3975 | 25 |
PageRank | References | Authors |
1.03 | 20 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vikraman Arvind | 1 | 296 | 38.18 |
| Johannes Köbler | 2 | 580 | 46.51 |