Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses

Full text

Pdf (800 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: 659 - 667

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Adam R. Klivans	Department of Mathematics, MIT, Cambridge, MA
Dieter van Melkebeek	Department of Computer Science, The University of Chicago, Chicago, IL

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 22, Citation Count: 16

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.301428 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.

	AK97	Vikraman Arvind , Johannes Köbler, On Resource-Bounded Measure and Pseudorandomness, Proceedings of the 17th Conference on Foundations of Software Technology and Theoretical Computer Science, p.235-249, December 18-20, 1997
	AKL+79	R. Aleliunas, R. Karp, R. Lipton, L. Lov,Ssz, and C. Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In Proceedings of the 20th IEEE Symposium on Foundations of Computer Science, pages 218-223. IEEE, 1979.
	Ang88	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	Bab85	L Babai, Trading group theory for randomness, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.421-429, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22192]
	BCG+96	Nader H. Bshouty , Richard Cleve , Ricard Gavaldà , Sampath Kannan , Christino Tamon, Oracles and queries that are sufficient for exact learning, Journal of Computer and System Sciences, v.52 n.3, p.421-433, June 1996 [doi>10.1006/jcss.1996.0032]
	BDG90	J. Balc,Szar, J. Dfaz, and $. Gabarr6. Structural Complexity II, volume 22 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1990.
	BDG95	José Luis Balcazar , Jose Diaz , Joaquim Gabarro, Structural complexity 1, Springer-Verlag New York, Inc., New York, NY, 1988
	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]
	BKL83	L. Bahai, W. Kantor, and E. Luks. Computational complexity and the classification of finite simple groups. In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, pages 162-171. IEEE, 1983.
	BL83	László Babai , Eugene M. Luks, Canonical labeling of graphs, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.171-183, December 1983 [doi>10.1145/800061.808746]
	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]
	BM88	László Babai , Shlomo Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class, Journal of Computer and System Sciences, v.36 n.2, p.254-276, April 1988 [doi>10.1016/0022-0000(88)90028-1]
	BNS92	László Babai , Noam Nisan , Márió Szegedy, Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs, Journal of Computer and System Sciences, v.45 n.2, p.204-232, Oct. 1992 [doi>10.1016/0022-0000(92)90047-M]
	CRT98	A. Clementi, I. Rotim, and L. Trevisan. Recent advances towards proving P = BPP. Bulletin of the European Association for Theoretical Computer Science, 64:96-103, February 1998.
	FFK94	Stephen A. Fenner , Lance J. Fortnow , Stuart A. Kurtz, Gap-definable counting classes, Journal of Computer and System Sciences, v.48 n.1, p.116-148, Feb. 1994 [doi>10.1016/S0022-0000(05)80024-8]
	For97	Lance Fortnow, Counting complexity, Complexity theory retrospective II, Springer-Verlag New York, Inc., New York, NY, 1998
	Fri90	J. Friedman. A note on matrix rigidity. Technical Report TR-308-91, Department of Computer Science, Princeton University, 1990.
	GMW91	Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
	GS89	S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In S. Micati, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 73-90. JAI Press, Greenwich, 1989.
	Imp95	R. Impagliazzo, Hard-core distributions for somewhat hard problems, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.538, October 23-25, 1995
	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]
	Lit88	Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
	LP82	H. Lewis and Ch. Papadimitriou. Symmetric spacebounded computation. Theoretical Computer Science, 19(2):161-I87, t982.
	Mil98	E Bro Miltersen. Relativizable pseudorandom generators and extractors. Comment to ECCC Technical Report TR98-055, 1998.
	Nis92	N. Nisan. Pseudorandom generators for spacebounded computation. Combinatorica, 12:449--461, 1992.
	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]
	Pap94	Ch. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
	PV91	P. Pudlfik and Z. Vavffn. Computation of rigidity of order n2/r for one simple matrix. Comment. Math. Univ. Carolinae, 32:213-218, 1991.
	PW90	Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]
	Raz	A. Razborov. On rigid matrices. Manuscript in Russian.
	Rud97	Steven Rudich, Super-bits, Demi-bits, and NP/qpoly-natural Proofs, Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science, p.85-93, July 11-12, 1997
	TO92	Seinosuke Toda , Mitsunori Ogiwara, Counting classes are at least as hard as the polynomial-time hierarchy, SIAM Journal on Computing, v.21 n.2, p.316-328, April 1992 [doi>10.1137/0221023]
	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]
	Tre98	L. Trevisan. Constructions of near-optimal extractors using pseudo-random generators. Technical Report TR-98-055, Electronic Colloquium on Computational Complexity, 1998.
	Vad98	S. Vadhan, Extracting all the Randomness from a Weakly Random Source, Massachusetts Institute of Technology, Cambridge, MA, 1998
	Val77	L. Valiant. Graph4heoretic arguments in low-level complexity. In Proceedings of the 6th Symposium on Mathematical Foundations of Computer Science, volume 53 of Lecture Notes in Computer Science, pages 162-176. Spfinger-Verlag, 1977.
	VV86	L. G. Valiant , V. V. Vazirani, NP is as easy as detecting unique solutions, Theoretical Computer Science, v.47 n.1, p.85-93, Nov. 1986
	Yao82	A. Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pages 80-91. IEEE, 1982.

CITED BY 16

	Christopher Umans, Pseudo-random generators for all hardnesses, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Salil Vadhan, On transformation of interactive proofs that preserve the prover's complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.200-207, May 21-23, 2000, Portland, Oregon, United States
	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
	Extractors and pseudorandom generators, Journal of the ACM (JACM), v.48 n.4, p.860-879, July 2001
	Russell Impagliazzo , Valentine Kabanets , Avi Wigderson, In search of an easy witness: exponential time vs. probabilistic polynomial time, Journal of Computer and System Sciences, v.65 n.4, p.672-694, December 2002
	Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Christopher Umans, Pseudo-random generators for all hardnesses, Journal of Computer and System Sciences, v.67 n.2, p.419-440, September 2003
	Oded Goldreich , Salil Vadhan , Avi Wigderson, On interactive proofs with a laconic prover, Computational Complexity, v.11 n.1/2, p.1-53, January 2003
	Dan Gutfreund , Ronen Shaltiel , Amnon Ta-Shma, Uniform hardness versus randomness tradeoffs for Arthur-Merlin games, Computational Complexity, v.12 n.3-4, p.85-130, September 2004
	Bella Dubrov , Yuval Ishai, On the randomness complexity of efficient sampling, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Minh-Huyen Nguyen , Salil Vadhan, Zero knowledge with efficient provers, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Jin-Yi Cai, S2p⊆ZPPNP, Journal of Computer and System Sciences, v.73 n.1, p.25-35, February, 2007
	Philippe Moser, Martingale families and dimension in P, Theoretical Computer Science, v.400 n.1-3, p.46-61, June, 2008
	Philippe Moser, Baire categories on small complexity classes and meager--comeager laws, Information and Computation, v.206 n.1, p.15-33, January, 2008
	Russell Impagliazzo , Philippe Moser, A zero-one law for RP and derandomization of AM if NP is not small, Information and Computation, v.207 n.7, p.787-792, July, 2009
	Scott Aaronson , Avi Wigderson, Algebrization: A New Barrier in Complexity Theory, ACM Transactions on Computation Theory (TOCT), v.1 n.1, p.1-54, February 2009