Self-testing/correcting with applications to numerical problems

DOI10.1016/0022-0000(93)90044-WzbMath0795.68131OpenAlexW3004537778WikidataQ62111468 ScholiaQ62111468MaRDI QIDQ1317490

Ronitt Rubinfeld, Michael Luby

Publication date: 18 September 1994

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(93)90044-w

zbMATH Keywords

matricesmultiplicationexponentiationprogram verificationinteger divisionprogram testingself-testing/correcting pairs

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Complexity and performance of numerical algorithms (65Y20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Matrix multiplication via arithmetic progressions
• Self-testing/correcting with applications to numerical problems
• Efficient checkers for number-theoretic computations
• Designing checkers for programs that run in parallel
• Gaussian elimination is not optimal
• Fast multiplication of large numbers
• Approximate formulas for some functions of prime numbers
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• A note on probabilistically verifying integer and polynomial products
• The Knowledge Complexity of Interactive Proof Systems
• Monte-Carlo approximation algorithms for enumeration problems
• Efficient generation of random nonsingular matrices
• Designing programs that check their work
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Related Items (only showing first 100 items - show all)

Sampling Correctors ⋮ Unnamed Item ⋮ An information-theoretic treatment of random-self-reducibility ⋮ Probabilistic proof systems — A survey ⋮ Simple analysis of graph tests for linearity and PCP ⋮ Cube Attack on Stream Ciphers using a Modified Linearity Test ⋮ Local Testing of Lattices ⋮ Checking properties of polynomials ⋮ Unnamed Item ⋮ Testing Linear-Invariant Properties ⋮ Reducing Testing Affine Spaces to Testing Linearity of Functions ⋮ On one-sided testing affine subspaces ⋮ Stability of approximate group actions: uniform and probabilistic ⋮ Unnamed Item ⋮ Erasures versus errors in local decoding and property testing ⋮ Testing membership for timed automata ⋮ Almost optimal proper learning and testing polynomials ⋮ \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Local-vs-global combinatorics ⋮ On Active and Passive Testing ⋮ NEW BOUNDS FOR SZEMERÉDI'S THEOREM, III: A POLYLOGARITHMIC BOUND FOR ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Brief Introduction to Property Testing ⋮ Introduction to Testing Graph Properties ⋮ On one-sided testing affine subspaces ⋮ Safety assurance via on-line monitoring ⋮ Program result checking: A new approach to making programs more reliable ⋮ Testing Euclidean Spanners ⋮ Hierarchy Theorems for Property Testing ⋮ Testing Odd Direct Sums Using High Dimensional Expanders ⋮ Sample-Based High-Dimensional Convexity Testing. ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Self-correcting for function fields of finite transcendental degree ⋮ Almost Optimal Testers for Concise Representations. ⋮ Testing problems with sublearning sample complexity ⋮ Testing commutativity of a group and the power of randomization ⋮ TESTING FOR FORBIDDEN POSETS IN ORDERED ROOTED FORESTS ⋮ Limitation on the Rate of Families of Locally Testable Codes ⋮ Testing Juntas: A Brief Survey ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Invariance in Property Testing ⋮ Testing Linear-Invariant Non-linear Properties: A Short Report ⋮ Optimal Testing of Reed-Muller Codes ⋮ Symmetric LDPC Codes and Local Testing ⋮ Some Recent Results on Local Testing of Sparse Linear Codes ⋮ Local Property Reconstruction and Monotonicity ⋮ Green’s Conjecture and Testing Linear Invariant Properties ⋮ Linear-consistency testing. ⋮ A Novel GPU-Based Implementation of the Cube Attack ⋮ A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Rigid matrices from rectangular PCPs ⋮ Fast distributed algorithms for testing graph properties ⋮ Hardness self-amplification: simplified, optimized, and unified ⋮ On approximability of satisfiable k-CSPs. III ⋮ A high dimensional Goldreich-Levin theorem ⋮ A unifying theory of distance from calibration ⋮ Unnamed Item ⋮ On the local leakage resilience of linear secret sharing schemes ⋮ More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP ⋮ No-signaling linear PCPs ⋮ Limitations of Local Filters of Lipschitz and Monotone Functions ⋮ Quasi-random words and limits of word sequences ⋮ On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing ⋮ On black-box verifiable outsourcing ⋮ The Fault Tolerance of NP-Hard Problems ⋮ Approximate Modularity Revisited ⋮ Concatenated kernel codes ⋮ Proximity Oblivious Testing and the Role of Invariances ⋮ Proximity Oblivious Testing and the Role of Invariances ⋮ Cube Attacks on Tweakable Black Box Polynomials ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Every Set in P Is Strongly Testable Under a Suitable Encoding ⋮ Almost optimal distribution-free junta testing ⋮ A unified framework for testing linear‐invariant properties ⋮ Relational Properties Expressible with One Universal Quantifier Are Testable ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ A combination of testability and decodability by tensor products ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Reed-Muller Codes ⋮ Direct Sum Testing ⋮ Algebraic testing and weight distributions of codes. ⋮ Testing Lipschitz functions on hypergrid domains ⋮ The power of adaptiveness and additional queries in random-self- reductions ⋮ Fast approximate probabilistically checkable proofs ⋮ Improving bounds on probabilistic affine tests to estimate the nonlinearity of Boolean functions ⋮ Testing graphs against an unknown distribution ⋮ Checker for data structures which sort elements ⋮ Testing Odd-Cycle-Freeness in Boolean Functions ⋮ An adaptivity hierarchy theorem for property testing ⋮ Empirical analysis of algorithms for the shortest negative cost cycle problem ⋮ High order differential attacks on stream ciphers

This page was built for publication: Self-testing/correcting with applications to numerical problems