Loading...
Please wait, while we are loading the content...
Similar Documents
Hardness and Hierarchy Theorems for Probabilistic Quasi-polynomial Time (extended abstract) (1999)
| Content Provider | CiteSeerX |
|---|---|
| Author | Cai, Jin-Yi Sivakumar, D. Nerurkar, Ajay P. |
| Abstract | We prove tight hierarchy theorems for bounded error probabilistic quasi-polynomial time classes, under several hardness assumptions. We show that assuming either (1) the Permanent does not have a subexponential time BP algorithm, or (2) some function in EXPTIME does not have subexponential size circuits, then for every 1 ff ! fi, BPTIME(2 (log n) ff ) $ BPTIME(2 (log n) fi ): Department of Computer Science, State University of New York at Buffalo, Buffalo, NY 14260. Email: cai@cs.buffalo.edu. Research supported in part by NSF grant CCR-9634665 and a J. S. Guggenheim Fellowship. y Department of Computer Science, State University of New York at Buffalo, Buffalo, NY 14260. Email: apn@cs.buffalo.edu. Research supported in part by NSF grant CCR-9634665. z Department of Computer Science, University of Houston, Houston, TX 77204. Email: siva@cs.uh.edu. Research supported in part by NSF CAREER award CCR-9734164. 1 Introduction It has been observed for some time now that the ... |
| File Format | |
| Publisher Date | 1999-01-01 |
| Access Restriction | Open |
| Subject Keyword | New York Probabilistic Quasi-polynomial Time Nsf Career Siva C Subexponential Time Bp Algorithm Subexponential Size Circuit Apn C Ff Fi Several Hardness Assumption Hierarchy Theorem Cai C Computer Science Tight Hierarchy Theorem Nsf Grant Ccr-9634665 State University Guggenheim Fellowship |
| Content Type | Text |
