New directions in testing
The DOI matches its Crossref record.
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
Cited by
Proof verification and the hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998) · Journal of the ACM · doi:10.1145/278298.278306 · Cited by 1,413
The computational complexity of linear optics
Aaronson, S., & Arkhipov, A. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993682 · Cited by 874
Raz, R., & Safra, S. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258641 · Cited by 834
Proof verification and hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1992) · Proceedings., 33rd Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267823 · Cited by 741
Decoding of Reed Solomon Codes beyond the Error-Correction Bound
Sudan, M. (1997) · Journal of Complexity · doi:10.1006/jcom.1997.0439 · Cited by 723
Self-testing/correcting with applications to numerical problems
Blum, M., Luby, M., & Rubinfeld, R. (1993) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(93)90044-w · Cited by 712
Algebraic methods for interactive proof systems
Lund, C., Fortnow, L., Karloff, H., & Nisan, N. (1992) · Journal of the ACM · doi:10.1145/146585.146605 · Cited by 711
Shamir, A. (1992) · Journal of the ACM · doi:10.1145/146585.146609 · Cited by 662
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
Non-deterministic exponential time has two-prover interactive protocols
Babai, L., Fortnow, L., & Lund, C. (1992) · Computational Complexity · doi:10.1007/bf01200430 · Cited by 520
Advanced structural health monitoring of concrete structures with the aid of acoustic emission
Behnia, A., Chai, H. K., & Shiotani, T. (2014) · Construction and Building Materials · doi:10.1016/j.conbuildmat.2014.04.103 · Cited by 447
Micali, S. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795284959 · Cited by 424
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
Designing programs that check their work
Blum, M., & Kannan, S. (1995) · Journal of the ACM · doi:10.1145/200836.200880 · 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
Self-testing/correcting with applications to numerical problems
Blum, M., Luby, M., & Rubinfeld, R. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100225 · Cited by 303
On the complexity and verification of quantum random circuit sampling
Bouland, A., Fefferman, B., Nirkhe, C., & Vazirani, U. (2019) · Nature Physics · doi:10.1038/s41567-018-0318-2 · Cited by 287
Designing programs that check their work
Blum, M., & Kanna, S. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73015 · Cited by 287
Modern Cryptography, Probabilistic Proofs and Pseudorandomness
Goldreich, O. (1999) · Algorithms and Combinatorics · doi:10.1007/978-3-662-12521-2 · Cited by 265
On the efficiency of local decoding procedures for error-correcting codes
Katz, J., & Trevisan, L. (2000) · Proceedings of the thirty-second annual ACM symposium on Theory of computing · doi:10.1145/335305.335315 · Cited by 264
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
Ishai, Y., & Kushilevitz, E. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892118 · Cited by 254
The overlap gap property: A topological barrier to optimizing over random structures
Gamarnik, D. (2021) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2108492118 · Cited by 103
How many qubits are needed for quantum computational supremacy?
Dalzell, A. M., Harrow, A. W., Koh, D. E., & La Placa, R. L. (2020) · Quantum · doi:10.22331/q-2020-05-11-264 · Cited by 88
“Finally, like worst-to-average-case reductions for computing the permanent [3, 41] or the output probability of a random quantum circuit [15, 48, 49], our reduction requires the computation of gap( g ) at each step to be exact, as any errors would be uncontrollably amplified by the recursion process.”
BackgroundContracting projected entangled pair states is average-case hard
Haferkamp, J., Hangleiter, D., Eisert, J., & Gluza, M. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.013010 · Cited by 62
Metadata
- Authors
- Lipton, R.
- Venue
- DIMACS Series in Discrete Mathematics and Theoretical Computer Science
- Publisher
- American Mathematical Society
- Published
- 1991-04-03
- Pages
- 1-1
- ISSN
- 1052-1798 (ISSN-L)
- 2472-4793
- OpenAlex
- W1596412683
- Cited by
- 255
- References
- 0
- FWCI
- 27.86
- Type
- book chapter
- Language
- en
- Open access
- closed
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.