Saving Queries With Randomness
| dc.contributor.author | Rohatgi, Pankaj | en_US |
| dc.date.accessioned | 2007-04-23T17:57:09Z | |
| dc.date.available | 2007-04-23T17:57:09Z | |
| dc.date.issued | 1991-12 | en_US |
| dc.description.abstract | In this paper, we provide tight bounds on the success probabilities of randomized reductions between various classes in the Boolean and Bounded Query Hierarchies. The P$^{SAT\Vert[k]}$ $\leq^{P}_{m}$ - complete language randomly reduces to a language in P$^{SAT\Vert[k-1]}$ with a one-sided error probability of 1/$\lceil$k/2$\rceil$. If two-sided error is allowed, then we show that a much lower error probability of 1/($k$ + 1) can be achieved. We prove that both these reductions are almost optimal by showing that the error probabilities cannot be reduced by even 1/poly, unless the PH collapses. These tight bounds precisely characterize the power and limitations of randomness in saving a query to SAT. These results can be used to identify optimal probability thresholds which determine when languages complete under randomized reductions inherit the hardness properties associated with $\leq^{P}_{m}$ - complete languages. Using these thresholds we prove hardness properties for some languages in these classes which are not $\leq^{P}_{m}$ - complete in certain relativized worlds. We also explore the relationship between randomization and functions computable using bounded queries to SAT. For any function $h (n) = O(log $n$), we show that there is a function $f$ computable using $h(n)$ nonadaptive queries to SAT, which cannot be computed correctly with probability 1/2+1/poly by any randomized machine which makes less than $h(n)$ adaptive queries to any oracle, unless PH collapses. | en_US |
| dc.format.extent | 1971770 bytes | |
| dc.format.extent | 412196 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1259 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/7099 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | Saving Queries With Randomness | en_US |
| dc.type | technical report | en_US |