Self-testing/correcting with applications to numerical problems
Open accessIntegrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
If the BLR test is run n times, then PC(K,V) can be concluded to be linear with probability 1-2^-n.
“If the BLR test is run n times, then we can conclude that PC(K,V) is linear with probability 1-2⁻ⁿ.”
From Cube attacks on round-reduced TinyJAMBU (2022) · cites this paper as [19]
Cites
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403 · see citing works
The knowledge complexity of interactive proof systems
Goldwasser, S., Micali, S., & Rackoff, C. (1989) · SIAM Journal on Computing · doi:10.1137/0218012 · Cited by 3,285 · see citing works
Gaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509 · see citing works
Approximate formulas for some functions of prime numbers
Rosser, J. B., & Schoenfeld, L. (1962) · Illinois Journal of Mathematics · doi:10.1215/ijm/1255631807 · Cited by 1,596 · see citing works
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
Blum, M., & Micali, S. M. (1984) · SIAM Journal on Computing · doi:10.1137/0213053 · Cited by 1,309 · see citing works
Self-citationSchnelle Multiplikation großer Zahlen
Schönhage, A., & Strassen, V. (1971) · Computing · doi:10.1007/bf02242355 · Cited by 1,107 · see citing works
Trading group theory for randomness
Babai, L. (1985) · doi:10.1145/22145.22192 · Cited by 781 · see citing works
Multi-prover interactive proofs: how to remove intractability
Ben-Or, M., Goldwasser, S., Kilian, J., & Widgerson, A. (1988) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/62212.62223 · Cited by 471 · see citing works
Monte-Carlo approximation algorithms for enumeration problems
Karp, R. M., Luby, M. G., & Madras, N. (1989) · Journal of Algorithms · doi:10.1016/0196-6774(89)90038-2 · Cited by 323 · see citing works
Self-citationLipton, R. B. (1991) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/002/13 · Cited by 257 · see citing works
Freivalds, R. (1979) · Lecture notes in computer science · doi:10.1007/3-540-09526-8_5 · Cited by 229 · see citing works
Self-testing/correcting for polynomials and for approximate functions
Gemmell, P. S., Lipton, R., Rubinfeld, R., Sudan, M., & Wigderson, A. (1991) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/103418.103429 · Cited by 184 · see citing works
Self-citationProceedings of the 42nd ACM symposium on Theory of computing
Mitzenmacher, M., & Schulman, L. J. (2010) · Cited by 160 · see citing works
A mathematical theory of self-checking, self-testing and self-correcting programs
Rubinfeld, R. (1991) · Cited by 53 · see citing works
Self-citationSelf-testing polynomial functions efficiently and over rational domains
Rubinfeld, R., & Sudan, M. (1992) · Cited by 42 · see citing works
Self-citationProgram result checking against adaptive programs and in cryptographic settings
Blum, M., Luby, M. G., & Rubinfeld, R. (1991) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/002/06 · Cited by 36 · see citing works
Self-citationEfficient generation of random nonsingular matrices
Randall, D. (1993) · Random Structures and Algorithms · doi:10.1002/rsa.3240040108 · Cited by 27 · see citing works
Efficient Checkers for Number-Theoretic Computations
Adleman, L. M., Huang, M. D., & Kompella, K. (1995) · Information and Computation · doi:10.1006/inco.1995.1125 · Cited by 21 · see citing works
Designing Checkers for Programs that Run in Parallel
Rubinfeld, R. (1996) · Algorithmica · doi:10.1007/bf01961540 · Cited by 16 · see citing works
Self-citationProgram Correctness: Can One Test For It?
Blum, M., & Raghavan, P. (1989) · IFIP Congress · Cited by 11 · see citing works
Self-citationA note on probabilistically verifying integer and polynomial products
Kaminski, M. (1989) · Journal of the ACM · doi:10.1145/58562.214082 · Cited by 10 · see citing works
Flagged first, then by citations
9 of the 30 references couldn’t be matched to a known paper.
Cited by
Sorted by citations
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902 · see citing works
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,449 · see citing works
Property testing and its connection to learning and approximation
Goldreich, O., Goldwasser, S., & Ron, D. (1998) · Journal of the ACM · doi:10.1145/285055.285060 · Cited by 1,019 · see citing works
Robust Characterizations of Polynomials with Applications to Program Testing
Rubinfeld, R., & Sudan, M. (1996) · SIAM Journal on Computing · doi:10.1137/s0097539793255151 · Cited by 794 · see citing works
Self-citationA Survey on Metamorphic Testing
Segura, S., Fraser, G., Sánchez, A. B., & Ruiz–Cortés, A. (2016) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2016.2532875 · Cited by 571 · see citing works
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
Bellare, M., Goldreich, O., & Sudan, M. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539796302531 · Cited by 454 · see citing works
Cube Attacks on Tweakable Black Box Polynomials
Dinur, I., & Shamir, A. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-01001-9_16 · Cited by 451 · see citing works
Fast batch verification for modular exponentiation and digital signatures
Mihir Bellare, Y., Garay, J. A., & Rabin, T. (1998) · Lecture notes in computer science · doi:10.1007/bfb0054130 · Cited by 447 · see citing works
How to Securely Outsource Cryptographic Computations
Hohenberger, S., & Lysyanskaya, A. (2005) · Lecture notes in computer science · doi:10.1007/978-3-540-30576-7_15 · Cited by 366 · see citing works
Self-testing of quantum systems: a review
Šupić, I., & Bowles, J. (2020) · Quantum · doi:10.22331/q-2020-09-30-337 · Cited by 365 · see citing works
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 342 · see citing works
New Algorithms for Secure Outsourcing of Modular Exponentiations
Chen, X., Li, J., Ma, J., Tang, Q., & Lou, W. (2013) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2013.180 · Cited by 317 · see citing works
Property Testing in Bounded Degree Graphs
Goldreich, O., & Ron (2002) · Algorithmica · doi:10.1007/s00453-001-0078-7 · Cited by 309 · see citing works
Free bits, PCPs and non-approximability-towards tight results
Bellare, M., Goldreich, O., & Sudan, M. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1995.492573 · Cited by 271 · see citing works
Verifiable Computation over Large Database with Incremental Updates
Chen, X., Li, J., Weng, J., Ma, J., & Lou, W. (2015) · IEEE Transactions on Computers · doi:10.1109/tc.2015.2512870 · Cited by 262 · see citing works
New Publicly Verifiable Databases with Efficient Updates
Chen, X., Li, J., Huang, X., Ma, J., & Lou, W. (2014) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2014.2366471 · Cited by 242 · see citing works
Vadhan, S. (2012) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000010 · Cited by 245 · see citing works
Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
Khot, S. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539705447037 · Cited by 236 · see citing works
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
Ben‐Sasson, E., Goldreich, O., Harsha, P., Sudan, M., & Vadhan, S. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539705446810 · Cited by 243 · see citing works
Verifying quantitative reliability for programs that execute on unreliable hardware
Carbin, M., Misailovíc, S., & Rinard, M. (2013) · Conference on Object-Oriented Programming Systems, Languages, and Applications · doi:10.1145/2509136.2509546 · Cited by 231 · see citing works
New Algorithms for Secure Outsourcing of Large-Scale Systems of Linear Equations
Chen, X., Huang, X., Li, J., Ma, J., Lou, W., & Wong, D. S. (2014) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2014.2363765 · Cited by 219 · see citing works
Software reliability via run-time result-checking
Wasserman, H., & Blum, M. (1997) · Journal of the ACM · doi:10.1145/268999.269003 · Cited by 192 · see citing works
Self-citationTwo Query PCP with Sub-Constant Error
Moshkovitz, D., & Raz, R. (2008) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.60 · Cited by 186 · see citing works
The hardness of approximate optima in lattices, codes, and systems of linear equations
Arora, S., Babai, L., Stern, J., & Sweedyk, Z. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1993.366815 · Cited by 182 · see citing works
Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., & Samorodnitsky, A. (2000) · COMBINATORICA · doi:10.1007/s004930070011 · Cited by 180 · see citing works
Fault-based testing without the need of oracles
Chen, T. Y., Tse, T. H., & Zhou, Z. Q. (2002) · Information and Software Technology · doi:10.1016/s0950-5849(02)00129-5 · Cited by 179 · see citing works
Linearity testing in characteristic two
Mihir Bellare, Y., Coppersmith, D., Håstad, J., Kiwi, M. A., & Sudan, M. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556674 · Cited by 172 · see citing works
Improved Low-Degree Testing and its Applications
Arora, S., & Sudan, M. (2003) · COMBINATORICA · doi:10.1007/s00493-003-0025-0 · Cited by 164 · see citing works
Testing Symmetric Properties of Distributions
Valiant, P. (2008) · SIAM Journal on Computing · doi:10.1137/080734066 · Cited by 157 · see citing works
Making argument systems for outsourced computation practical (sometimes)
Setty, S., McPherson, R., Blumberg, A. J., & Walfish, M. (2012) · Cited by 151 · see citing works
Locally testable codes and PCPs of almost-linear length
Goldreich, O., & Sudan, M. (2006) · Journal of the ACM · doi:10.1145/1162349.1162351 · Cited by 152 · see citing works
A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
Alon, N., Fischer, E., Newman, I., & Shapira, A. (2009) · SIAM Journal on Computing · doi:10.1137/060667177 · Cited by 151 · see citing works
A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
Alon, N., & Shapira, A. (2008) · SIAM Journal on Computing · doi:10.1137/06064888x · Cited by 151 · see citing works
Improved low-degree testing and its applications
Arora, S., & Sudan, M. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258642 · Cited by 150 · see citing works
Yekhanin, S. (2012) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000030 · Cited by 147 · see citing works
Improved Testing Algorithms for Monotonicity
Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D., & Samorodnitsky, A. (1999) · Lecture notes in computer science · doi:10.1007/978-3-540-48413-4_10 · Cited by 144 · see citing works
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
Ben‐Sasson, E., Sudan, M., Vadhan, S., & Wigderson, A. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780631 · Cited by 140 · see citing works
Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S. N., & Ron, D. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.856958 · Cited by 140 · see citing works
Kaufman, T., & Sudan, M. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374434 · Cited by 136 · see citing works
Property testing in bounded degree graphs
Goldreich, O., & Ron, D. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258627 · Cited by 133 · see citing works
Every minor-closed property of sparse graphs is testable
Benjamini, I., Schramm, O., & Shapira, A. (2008) · Advances in Mathematics · doi:10.1016/j.aim.2009.10.018 · Cited by 132 · see citing works
Property Testing Lower Bounds via Communication Complexity
Blais, E., Brody, J., & Matulef, K. (2012) · Computational Complexity · doi:10.1007/s00037-012-0040-x · Cited by 131 · see citing works
Low-degree tests at large distances
Samorodnitsky, A. (2007) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1250790.1250864 · Cited by 131 · see citing works
Property Testing: A Learning Theory Perspective
Ron, D. (2008) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000004 · Cited by 132 · see citing works
On Worst‐Case to Average‐Case Reductions for NP Problems
Bogdanov, A., & Trevisan, L. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2003.1238205 · Cited by 130 · see citing works
A Sublinear Bipartiteness Tester for Bounded Degree Graphs
Goldreich, O., & Ron, D. (1999) · COMBINATORICA · doi:10.1007/s004930050060 · Cited by 129 · see citing works
Some Applications of Coding Theory in Computational ComplexityPreprint
Trevisan, L. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0409044 · Cited by 147 · see citing works
Taking proof-based verified computation a few steps closer to practicality
Setty, S., Vu, V., Panpalia, N., Braun, B., Blumberg, A. J., & Walfish, M. (2012) · Cited by 131 · see citing works
Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique
Khot, S. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.59 · Cited by 124 · see citing works
Efficient Arguments without Short PCPs
Ishai, Y., Eyal Kushilevitz, Z., & Ostrovsky, R. (2007) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2007.10 · Cited by 123 · see citing works
New Algorithms for Secure Outsourcing of Modular Exponentiations
Chen, X., Li, J., Ma, J., Tang, Q., & Lou, W. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33167-1_31 · Cited by 120 · see citing works
Ergün, F., Kannan, S., Kumar, S. R. V., Rubinfeld, R., & Viswanathan, M. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.1999.1692 · Cited by 120 · see citing works
Self-citationTesting Basic Boolean Formulae
Parnas, M., Ron, D., & Samorodnitsky, A. (2002) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480101407444 · Cited by 108 · see citing works
Lu, C.-J., Reingold, O., Vadhan, S., & Wigderson, A. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780630 · Cited by 108 · see citing works
Case studies on the selection of useful relations in metamorphic testing
Chen, T. Y., Huang, D., Tse, T.-H., & Zhou, Z. Q. (2004) · Swinburne figshare (Swinburne University of Technology) · Cited by 108 · see citing works
Yekhanin, S. (2011) · now publishers, Inc. eBooks · doi:10.1561/9781601985453 · Cited by 105 · see citing works
Testing for Concise Representations
Diakonikolas, I., Lee, H. K., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R. A., & Wan, A. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.32 · Cited by 105 · see citing works
Self-citationClustered Integer 3SUM via Additive Combinatorics
Chan, T. M., & Lewenstein, M. (2015) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2746539.2746568 · Cited by 103 · see citing works
Rubinfeld, R., & Shapira, A. (2011) · SIAM Journal on Discrete Mathematics · doi:10.1137/100791075 · Cited by 102 · see citing works
Self-citationTesting Product States, Quantum Merlin-Arthur Games and Tensor Optimization
Harrow, A. W., & Montanaro, A. (2013) · Journal of the ACM · doi:10.1145/2432622.2432625 · Cited by 102 · see citing works
Testing Low-Degree Polynomials over GF(2)
Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S. N., & Ron, D. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45198-3_17 · Cited by 102 · see citing works
Gowers uniformity, influence of variables, and PCPs
Samorodnitsky, A., & Trevisan, L. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132519 · Cited by 100 · see citing works
A combinatorial characterization of the testable graph properties
Alon, N., Fischer, E., Newman, I., & Shapira, A. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132555 · Cited by 100 · see citing works
Pseudorandomness and Average-Case Complexity Via Uniform Reductions
Trevisan, L., & Vadhan, S. (2007) · Computational Complexity · doi:10.1007/s00037-007-0233-x · Cited by 96 · see citing works
Metamorphic Testing and Its Applications
Zhou, Z. Q., Huang, D., Tse, T. H., Yang, Z., Huang, H., & Chen, T. Y. (2004) · Cited by 94 · see citing works
A Survey of Quantum Property Testing
Montanaro, A., & de Wolf, R. (2016) · Theory of Computing · doi:10.4086/toc.gs.2016.007 · Cited by 135 · see citing works
Robust pcps of proximity, shorter pcps and applications to coding
Ben‐Sasson, E., Goldreich, O., Harsha, P., Sudan, M., & Vadhan, S. (2004) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1007352.1007361 · Cited by 83 · see citing works
Optimal Testing of Reed-Muller Codes
Bhattacharyya, A., Kopparty, S., Schoenebeck, G. R., Sudan, M., & Zuckerman, D. (2010) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.54 · Cited by 81 · see citing works
A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers
Ito, T., & Vidick, T. (2012) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.11 · Cited by 81 · see citing works
Property testing and its connection to learning and approximation
Goldreich, O., Goldwasser, S., & Ron, D. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1996.548493 · Cited by 82 · see citing works
Recent progress in exact geometric computation
Li, C., Pion, S., & Yap, C. K. (2005) · The Journal of Logic and Algebraic Programming · doi:10.1016/j.jlap.2004.07.006 · Cited by 77 · see citing works
The approximability of NP-hard problems
Arora, S. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276784 · Cited by 75 · see citing works
On Proximity-Oblivious Testing
Goldreich, O., & Ron, D. (2009) · SIAM Journal on Computing · doi:10.1137/100789646 · Cited by 72 · see citing works
Simple analysis of graph tests for linearity and PCP
Håstad, J., & Wigderson, A. (2003) · Random Structures and Algorithms · doi:10.1002/rsa.10068 · Cited by 72 · see citing works
Metamorphic Testing and Beyond
Chen, T. Y., Kuo, F., Tse, T. H., & Zhou, Z. Q. (2005) · International Workshop on Software Technology and Engineering Practice (STEP) · doi:10.1109/step.2003.18 · Cited by 71 · see citing works
The distribution of polynomials over finite fields, with applications to the Gowers norms
Green, B., & Tao, T. (2007) · Libraries and Cultural Resources (University of Calgary) · doi:10.11575/cdm.v4i2.62086 · Cited by 69 · see citing works
Matulef, K., O’Donnell, R., Rubinfeld, R., & Servedio, R. A. (2010) · SIAM Journal on Computing · doi:10.1137/070707890 · Cited by 68 · see citing works
Self-citationEfficient algorithms for secure outsourcing of bilinear pairings
Chen, X., Susilo, W., Li, J., Wong, D. S., Ma, J., Tang, S., & Tang, Q. (2014) · Theoretical Computer Science · doi:10.1016/j.tcs.2014.09.038 · Cited by 66 · see citing works
Proofs, Arguments, and Zero-Knowledge
Thaler, J. (2022) · Foundations and Trends® in Privacy and Security · doi:10.1561/3300000030 · Cited by 70 · see citing works
Testing for Concise Representations
Diakonikolas, I., Lee, H., Matule, K., Onak, K., Rubinfeld, R., Servedio, R. A., & Wan, A. (2007) · Cited by 67 · see citing works
Self-citationA Characterization of the (natural) Graph Properties Testable with One-Sided Error
Alon, N., & Shapira, A. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.5 · Cited by 67 · see citing works
Publicly verifiable privacy-preserving aggregation and its application in IoT
Li, T., Gao, C., Jiang, L., Pedrycz, W., & Shen, J. (2018) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2018.09.018 · Cited by 65 · see citing works
Verifying quantitative reliability for programs that execute on unreliable hardware
Carbin, M., Misailovíc, S., & Rinard, M. (2013) · ACM SIGPLAN Notices · doi:10.1145/2544173.2509546 · Cited by 65 · see citing works
Reflections on the Pentium division bug
Blum, M., & Wasserman, H. (1996) · IEEE Transactions on Computers · doi:10.1109/12.494097 · Cited by 64 · see citing works
Self-citationWitness-based cryptographic program checking and robust function sharing
Frankel, Y., Gemmell, P. S., & Yung, M. M. (1996) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/237814.237998 · Cited by 63 · see citing works
Pseudorandomness and average-case complexity via uniform reductions
Trevisan, L., & Vadhan, S. (2003) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2002.1004348 · Cited by 61 · see citing works
Robust Locally Testable Codes and Products of Codes
Ben‐Sasson, E., & Sudan, M. (2004) · Random Structures and Algorithms · doi:10.1002/rsa.20120 · Cited by 60 · see citing works
A quantum linearity test for robustly verifying entanglement
Natarajan, A., & Vidick, T. (2017) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3055399.3055468 · Cited by 59 · see citing works
Reconstructing Algebraic Functions from Mixed Data
Ar, S., Lipton, R. J., Rubinfeld, R., & Sudan, M. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539796297577 · Cited by 59 · see citing works
Self-citationSelf-testing of Quantum Circuits
Magniez, F., Mayers, D., Mosca, M., & Ollivier, H. (2006) · Lecture Notes in Computer Science · doi:10.1007/11786986_8 · Cited by 58 · see citing works
Local Hamiltonians Whose Ground States Are Hard to Approximate
Eldar, L., & Harrow, A. W. (2017) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2017.46 · Cited by 58 · see citing works
Testing versus Estimation of Graph Properties
Fischer, E., & Newman, I. (2007) · SIAM Journal on Computing · doi:10.1137/060652324 · Cited by 58 · see citing works
Ergün, F., Kannan, S., Kumar, S. R., Rubinfeld, R., & Viswanathan, M. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276757 · Cited by 58 · see citing works
Self-citationTesting Fourier Dimensionality and Sparsity
Gopalan, P., O’Donnell, R., Servedio, R. A., Shpilka, A., & Wimmer, K. (2011) · SIAM Journal on Computing · doi:10.1137/100785429 · Cited by 56 · see citing works
On the Advantage over Random for Maximum Acyclic Subgraph
Charikar, M., Makarychev, K., & Maka, Y. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.65 · Cited by 56 · see citing works
Combinatorial Construction of Locally Testable Codes
Meir, O. (2008) · SIAM Journal on Computing · doi:10.1137/080729967 · Cited by 56 · see citing works
High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
Kopparty, S., Meir, O., Ron‐Zewi, N., & Saraf, S. (2017) · Journal of the ACM · doi:10.1145/3051093 · Cited by 55 · see citing works
A lower bound for testing juntas
Chockler, H., & Gutfreund, D. (2004) · Information Processing Letters · doi:10.1016/j.ipl.2004.01.023 · Cited by 54 · see citing works
Testing Polynomials over General Fields
Kaufman, T., & Ron, D. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704445615 · Cited by 54 · see citing works
List-decoding reed-muller codes over small fields
Gopalan, P., Klivans, A. R., & Zuckerman, D. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374417 · Cited by 54 · see citing works
- Authors
- Blum, M., Luby, M., & Rubinfeld, R.
- Affiliations
- University of California, Berkeley (US)
- International Computer Science Institute (US)
- Cornell University (US)
- Venue
- Journal of Computer and System Sciences
- Publisher
- Elsevier BV
- Published
- 1993-12
- Volume
- 47
- Issue
- 3
- Pages
- 549-595
- ISSN
- 0022-0000 (ISSN-L)
- OpenAlex
- W3004537778
- Cited by
- 712
- References
- 30
- Citations by year
- 2026: 4 · 2025: 12 · 2024: 8 · 2023: 8 · 2022: 23 · 2021: 19 · 2020: 26 · 2019: 17 · 2018: 24 · 2017: 21 · 2016: 31 · 2015: 27 · 2014: 25 · 2013: 35 · 2012: 33
- FWCI
- 6.50
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Licence
- Locations
- Journal of Computer and System Sciences (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, programming, and type systems
- Keywords
- fault-tolerant computation, numerical algorithms, integer multiplication, modular multiplication, matrix multiplication, matrix inversion, matrix determinants, matrix rank, integer division, modular exponentiation, polynomial multiplication, program correctness
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
