The DOI matches its Crossref record; 33 of the 33 references it cites were found in a registry or an index.
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
Open accessAbstract
Traditional hardness versus randomness results focus on time-efficient randomized decision procedures. We generalize these trade-offs to a much wider class of randomized processes. We work out various applications, most notably to derandomizing Arthur-Merlin games. We show that every language with a bounded round Arthur-Merlin game has subexponential size membership proofs for infinitely many input lengths unless exponential time coincides with the third level of the polynomial-time hierarchy (and hence the polynomial-time hierarchy collapses). Since the graph nonisomorphism problem has a bounded round Arthur-Merlin game, this provides the first strong evidence that graph nonisomorphism has subexponential size proofs. We also establish hardness versus randomness trade-offs for space bounded computation.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
Goldwasser, S., & Micali, S. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,603
Angluin, D. (1988) · Machine Learning · doi:10.1007/bf00116828 · Cited by 1,905
Goldreich, O., Micali, S., & Wigderson, A. (1991) · Journal of the ACM · doi:10.1145/116825.116852 · Cited by 1,349
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
Blum, M., & Micali, S. (1984) · SIAM Journal on Computing · doi:10.1137/0213053 · Cited by 1,322
Theory and application of trapdoor functions
Yao, A. C.-C. (1982) · doi:10.1109/sfcs.1982.95 · Cited by 1,008
Luis Balcázar, J., Díaz, J., & Gabarró, J. (1995) · Texts in Theoretical Computer Science An EATCS Series · doi:10.1007/978-3-642-79235-9 · Cited by 866
Nisan, N., & Wigderson, A. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80043-1 · Cited by 808
Trading group theory for randomness
Babai, L. (1985) · Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85 · doi:10.1145/22145.22192 · Cited by 772
Random walks, universal traversal sequences, and the complexity of maze problems
Aleliunas, R., Karp, R. M., Lipton, R. J., Lovasz, L., & Rackoff, C. (1979) · 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) · doi:10.1109/sfcs.1979.34 · Cited by 692
PP is as Hard as the Polynomial-Time Hierarchy
Toda, S. (1991) · SIAM Journal on Computing · doi:10.1137/0220053 · Cited by 665
NP is as easy as detecting unique solutions
Valiant, L. G., & Vazirani, V. V. (1986) · Theoretical Computer Science · doi:10.1016/0304-3975(86)90135-0 · Cited by 635
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
Babai, L., & Moran, S. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90028-1 · Cited by 589
P = BPP if E requires exponential circuits: derandomizing the XOR lemma
Impagliazzo, R., & Wigderson, A. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258590 · Cited by 534
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm
Littlestone, N. (1988) · Machine Learning · doi:10.1007/bf00116827 · Cited by 497
Babai, L., & Luks, E. M. (1983) · Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83 · doi:10.1145/800061.808746 · Cited by 410
Private coins versus public coins in interactive proof systems
Goldwasser, S., & Sipser, M. (1986) · Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 · doi:10.1145/12130.12137 · Cited by 399
Pseudorandom Generators without the XOR Lemma
Sudan, M., Trevisan, L., & Vadhan, S. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2000.1730 · Cited by 393
Graph-theoretic arguments in low-level complexity
Valiant, L. G. (1977) · Lecture Notes in Computer Science · doi:10.1007/3-540-08353-7_135 · Cited by 312
BPP has subexponential time simulations unlessEXPTIME has publishable proofs
Babai, L., Fortnow, L., Nisan, N., & Wigderson, A. (1993) · Computational Complexity · doi:10.1007/bf01275486 · Cited by 310
Hard-core distributions for somewhat hard problems
Impagliazzo, R. (2002) · Proceedings of IEEE 36th Annual Foundations of Computer Science · doi:10.1109/sfcs.1995.492584 · Cited by 254
On the power of two-point based sampling
Chor, B., & Goldreich, O. (1989) · Journal of Complexity · doi:10.1016/0885-064x(89)90015-0 · Cited by 191
Symmetric space-bounded computation
Lewis, H. R., & Papadimitriou, C. H. (1982) · Theoretical Computer Science · doi:10.1016/0304-3975(82)90058-5 · Cited by 171
Gap-definable counting classes
Fenner, S. A., Fortnow, L. J., & Kurtz, S. A. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80024-8 · Cited by 170
Oracles and Queries That Are Sufficient for Exact Learning
Bshouty, N. H., Cleve, R., Gavaldà, R., Kannan, S., & Tamon, C. (1996) · Journal of Computer and System Sciences · doi:10.1006/jcss.1996.0032 · Cited by 166
Prediction-preserving reducibility
Pitt, L., & Warmuth, M. K. (1990) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(90)90028-j · Cited by 159
Extracting Randomness: A Survey and New Constructions
Nisan, N., & Ta‐Shma, A. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1546 · Cited by 158
Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
Toda, S., & Ogiwara, M. (1992) · SIAM Journal on Computing · doi:10.1137/0221023 · Cited by 126
Computational complexity and the classification of finite simple groups
Babai, L., Kantor, W. M., & Luks, E. M. (1983) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1983.10 · Cited by 123
Short propositional formulas represent nondeterministic computations
Cook, S. A. (1988) · Information Processing Letters · doi:10.1016/0020-0190(88)90152-4 · Cited by 73
Fortnow, L. (1997) · Springer eBooks · doi:10.1007/978-1-4612-1872-2_4 · Cited by 63
Constructions of Near-Optimal Extractors Using Pseudo-Random Generators
Trevisan, L. (1998) · Cited by 17
Cited by
Undirected connectivity in log-space
Reingold, O. (2008) · Journal of the ACM · doi:10.1145/1391289.1391291 · Cited by 505
Pseudorandom Generators without the XOR Lemma
Sudan, M., Trevisan, L., & Vadhan, S. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2000.1730 · Cited by 393
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds
Kabanets, V., & Impagliazzo, R. (2004) · computational complexity · doi:10.1007/s00037-004-0182-6 · Cited by 378
Extractors and pseudorandom generators
(2001) · Journal of the ACM · doi:10.1145/502090.502099 · Cited by 324
Infeasibility of instance compression and succinct PCPs for NP
Fortnow, L., & Santhanam, R. (2011) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2010.06.007 · Cited by 288
Metadata
- Authors
- Klivans, A. R., & van Melkebeek, D.
- Venue
- SIAM Journal on Computing
- Published
- 2002-01
- Volume
- 31
- Issue
- 5
- Pages
- 1501-1526
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W1558847040
- Cited by
- 270
- References
- 33
- FWCI
- 11.43
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.