Self-testing/correcting with applications to numerical problems

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

Ronitt Rubinfeld, Michael Luby, Manuel Blum

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

matrices multiplication exponentiation program verification integer division program testing self-testing/correcting pairs

Mathematics Subject Classification ID

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

Related Items

Sampling Correctors, 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, 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 CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING, Unnamed Item, Unnamed Item, Fast distributed algorithms for testing graph properties, 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, 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, Applying cube attacks to stream ciphers in realistic scenarios, A self-tester for linear functions over the integers with an elementary proof of correctness, Testing nonlinear operators, The hardness of approximate optima in lattices, codes, and systems of linear equations, Learning fallible deterministic finite automata, An optimal tester for $k$-linear, A lower bound for testing juntas, A query efficient non-adaptive long code test with perfect completeness, Large values of the Gowers-Host-Kra seminorms, Designing checkers for programs that run in parallel, A survey on delegated computation, Nearly complete graphs decomposable into large induced matchings and their applications, Secure outsourcing of modular exponentiations under single untrusted programme model, Property testing and expansion in cubical complexes, Low redundancy polynomial checks for numerical computation, Property testing for cyclic groups and beyond, Improving Key Recovery to 784 and 799 Rounds of Trivium Using Optimized Cube Attacks, Checking the correctness of memories, Indistinguishability and First-Order Logic, Fault detection tests for stuck-at faults on parity counter inputs, A quantum algorithm to estimate the Gowers $U_2$ norm and linearity testing of Boolean functions, Approximate testing with error relative to input size., Quantum property testing of group solvability, On the derandomization of the graph test for homomorphism over groups, An optimal tester for $k$-Linear, 2-transitivity is insufficient for local testability, Hierarchy theorems for property testing, Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting), Local correction of juntas, Approximately classic judgement aggregation, Testable and untestable classes of first-order formulae, Efficient and secure delegation of exponentiation in general groups to a single malicious server, Efficiently testing sparse $\text{GF}(2)$ polynomials, Locality and checkability in wait-free computing, A property tester for tree-likeness of quartet topologies, Testing consistency of quartet topologies: a parameterized approach, On-line approximate string matching with bounded errors, Certifying algorithms, Distribution-free connectivity testing for sparse graphs, Finding large 3-free sets. I. The small $n$ case, On the Query Complexity of Testing Orientations for Being Eulerian, Breaking the ε-Soundness Bound of the Linearity Test over GF(2), Property-preserving data reconstruction, Efficient algorithms for secure outsourcing of bilinear pairings, The power and limitations of uniform samples in testing properties of figures, Testing of matrix-poset properties, Property testing of regular tree languages, Composition of semi-LTCs by two-wise tensor products, Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas, Lower Bounds for Testing Computability by Small Width OBDDs, A separation theorem in property testing, Observing biases in the state: case studies with Trivium and Trivia-SC, Symmetric LDPC codes and local testing, Pipelined algorithms to detect cheating in long-term grid computations, Property testing lower bounds via a generalization of randomized parity decision trees, Every minor-closed property of sparse graphs is testable, Property testing lower bounds via communication complexity, New publicly verifiable computation for batch matrix multiplication, Testing convexity properties of tree colorings, On the structure of Boolean functions with small spectral norm, The fault tolerance of NP-hard problems, Testing hypergraph colorability, A non-extendibility certificate for submodularity and applications, Recent progress in exact geometric computation, Testing low-degree polynomials over prime fields, Smooth and strong PCPs, Hierarchy theorems for testing properties in size-oblivious query complexity, Tolerant property testing and distance approximation, Three-Player Entangled XOR Games are NP-Hard to Approximate, Limits on the Rate of Locally Testable Affine-Invariant Codes, A Canonical Form for Testing Boolean Function Properties, Short Locally Testable Codes and Proofs, A Brief Introduction to Property Testing, Introduction to Testing Graph Properties, A combinatorial characterization of smooth LTCs and applications, Subversion-resilient public key encryption with practical watchdogs, Locality and Checkability in Wait-Free Computing, Testing properties of functions on finite groups, Characterizations of locally testable linear- and affine-invariant families, Testing computability by width-two OBDDs, Self-correctors for Cryptographic Modules, Spot-checkers, Testing algebraic geometric codes, Robust characterizations of k -wise independence over product spaces and related testing results, On Dinur’s proof of the PCP theorem, Quantum cryptographic property testing of multi-output Boolean functions, Local correctability of expander codes, Self-testing/correcting with applications to numerical problems, Exponentially improved algorithms and lower bounds for testing signed majorities

Cites Work