Hardness and hierarchy theorems for probabilistic quasi-polynomial time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Hardness and hierarchy theorems for probabilistic quasi-polynomial time

Full text

Pdf (774 KB)

Source

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

Atlanta, Georgia, United States

Pages: 726 - 735

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Jin-Yi Cai	Department of Computer Science, State Unviersity of New York at Buffalo, Baffalo, NY
Ajay Nerurkar	Department of Computer Science, State University of New York at Buffalo, Buffalo, NY
D. Sivakumar	Department of Computer Science, University of Houston, Houston, TX

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 16, 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/301250.301444 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.

	ABHH93	Eric Allender , Richard Beigel , Ulrich Hertrampf , Steven Homer, Almost-everywhere complexity hierarchies for nondeterministic time, Theoretical Computer Science, v.115 n.2, p.225-241, July 19, 1993 [doi>10.1016/0304-3975(93)90117-C]
	BFNW93	László Babai , Lance Fortnow , Noam Nisan , Avi Wigderson, BPP has subexponential time simulations unless EXPTIME has publishable proofs, Computational Complexity, v.3 n.4, p.307-318, Oct. 1993 [doi>10.1007/BF01275486]
	BH97	C. Berg and J. H~tad. On the BPP hierarchy problem. Technical Report TRITA NA 97-02, Royal Institute of Technology, 1997.
	BM84	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	Coo73	S.A. Cook. A hierarchy for nondeterministic time complexity. Journal of Computer and System Sciences, 7(4):343-353, August 1973.
	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]
	FS97	Lance Fortnow , Michael Sipser, Retraction of probabilistic computation and linear time, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.750, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258677]
	GHS91	John G. Geske , Dung T. Huynh , Joel I. Seiferas, A note on almost-everywhere-complex sets and separating deterministic-time-complexity classes, Information and Computation, v.92 n.1, p.97-104, May 1991 [doi>10.1016/0890-5401(91)90022-T]
	GL89	O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
	HS65	J. Hartmanis and R. E. Stearns. On the computational complexity of algorithms. Trans. Amer. Math. Soc., 117:285-306, 1965.
	HS66	F. C. Hennie , R. E. Stearns, Two-Tape Simulation of Multitape Turing Machines, Journal of the ACM (JACM), v.13 n.4, p.533-546, Oct. 1966 [doi>10.1145/321356.321362]
	IW97	Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258590]
	IW98	R. Impagliazzo , A. Wigderson, Randomness vs. Time: De-Randomization under a Uniform Assumption, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.734, November 08-11, 1998
	KL80	Richard M. Karp , Richard J. Lipton, Some connections between nonuniform and uniform complexity classes, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.302-309, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804678]
	KV87	Marek Karpinski , Rutger Verbeek, Randomness, provability, and the separation of Monte Carlo time and space, Computation theory and logic, Springer-Verlag, London, 1987
	NW94	Noam Nisan , Avi Wigderson, Hardness vs. randomness, Journal of Computer and System Sciences, v.49 n.2, p.149-167, Oct. 1994 [doi>10.1016/S0022-0000(05)80043-1]
	SFM78	Joel I. Seiferas , Michael J. Fischer , Albert R. Meyer, Separating Nondeterministic Time Complexity Classes, Journal of the ACM (JACM), v.25 n.1, p.146-167, Jan. 1978 [doi>10.1145/322047.322061]
	Tod91	Seinosuke Toda, PP is as hard as the polynomial-time hierarchy, SIAM Journal on Computing, v.20 n.5, p.865-877, Oct. 1991 [doi>10.1137/0220053]
	Yao82	A C. Yao. Theory and applications of trapdoor functions (extended abstract). In Proc. 23rd FOCS, pages 80-91, 1982.

CITED BY 2

	Russell Impagliazzo , Ronen Shaltiel , Avi Wigderson, Extractors and pseudo-random generators with optimal seed length, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.1-10, May 21-23, 2000, Portland, Oregon, United States
	Luca Trevisan , Salil Vadhan, Pseudorandomness and Average-Case Complexity Via Uniform Reductions, Computational Complexity, v.16 n.4, p.331-364, December 2007