Retraction of probabilistic computation and linear time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Retraction of probabilistic computation and linear time

Full text

Pdf (288 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents

El Paso, Texas, United States

Page: 750

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Lance Fortnow	Computer Science Dept., University of Chicago, Chicago, IL and MIT Math Dept., Cambridge, MA
Michael Sipser	MIT Math Dept., Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 22, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/258533.258677 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BH97	Christer Berg and Johan H&stad. On the BPP hierarchy problem. Technical Report TRITA-NA-9702, Royal Institute of Tecnology, 1997.
	FL93	Lance Fortnow , Carsten Lund, Interactive proof systems and alternating time-space complexity, Theoretical Computer Science, v.113 n.1, p.55-73, May 24, 1993
	FS89	L. Fortnow , M. Sipser, Probabilistic computation and linear time, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.148-156, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73021]
	LFKN92	Carsten Lund , Lance Fortnow , Howard Karloff, Algebraic methods for interactive proof systems, Journal of the ACM (JACM), v.39 n.4, p.859-868, Oct. 1992 [doi>10.1145/146585.146605]
	Sha92	Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]

CITED BY 2

	Jin-Yi Cai , Ajay Nerurkar , D. Sivakumar, Hardness and hierarchy theorems for probabilistic quasi-polynomial time, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.726-735, May 01-04, 1999, Atlanta, Georgia, United States
	Dieter Melkebeek , Konstantin Pervyshev, A Generic Time Hierarchy with One Bit of Advice, Computational Complexity, v.16 n.2, p.139-179, May 2007