Designing programs that check their work
From MaRDI portal
Publication:4369864
DOI10.1145/200836.200880zbMath0886.68046OpenAlexW1996839061MaRDI QIDQ4369864
Publication date: 2 February 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/200836.200880
Related Items
New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes., Algebraic testing and weight distributions of codes., The power of adaptiveness and additional queries in random-self- reductions, Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints, Fast approximate probabilistically checkable proofs, Checker for data structures which sort elements, An information-theoretic treatment of random-self-reducibility, On the power of multi-prover interactive protocols, The Journey from NP to TFNP Hardness, Test suite oscillations, 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, A survey on delegated computation, Secure outsourcing of modular exponentiations under single untrusted programme model, On locally decodable codes, self-correctable codes, and \(t\)-private PIR, Linear-size constant-query IOPs for delegating computation, Low redundancy polynomial checks for numerical computation, Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces, Checking the convexity of polytopes and the planarity of subdivisions (extended abstract), Checking the correctness of memories, On the Complexity of the Hidden Subgroup Problem, Testing membership for timed automata, Approximate testing with error relative to input size., \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem, Unnamed Item, Construction sequences and certifying 3-connectivity, A note on the self-witnessing property of computational problems, Nearly exact mining of frequent trees in large networks, Efficient and secure delegation of exponentiation in general groups to a single malicious server, On matrix rigidity and locally self-correctable codes, Unnamed Item, Locality and checkability in wait-free computing, Certifying algorithms, Foundations of Homomorphic Secret Sharing, Program result checking: A new approach to making programs more reliable, Property testing of regular tree languages, A self-certifying compilation framework for WebAssembly, Self-correcting for function fields of finite transcendental degree, An efficient local approach to convexity testing of piecewise-linear hypersurfaces, Batch checking with applications to linear functions, Pipelined algorithms to detect cheating in long-term grid computations, A framework for developing stand-alone certifiers, ON THE COMPLEXITY OF THE HIDDEN SUBGROUP PROBLEM, Problem identification using program checking, Efficient authenticated data structures for graph connectivity and geometric search problems, Speeding up exponentiation using an untrusted computational resource, Deterministically testing sparse polynomial identities of unbounded degree, Finding paths of length \(k\) in \(O^{*}(2^k)\) time, A nonadaptive NC checker for permutation group intersection, Linear-consistency testing., A low complexity probabilistic test for integer multiplication, Recent progress in exact geometric computation, A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING, Lower Bounds on Assumptions Behind Indistinguishability Obfuscation, Quasi-random words and limits of word sequences, High-entropy dual functions over finite fields and locally decodable codes, Locality and Checkability in Wait-Free Computing, Checking the convexity of polytopes and the planarity of subdivisions, Outlaw distributions and locally decodable codes, Spot-checkers, AUTOMATIC RESULT VERIFICATION BY COMPLETE RUN-TIME CHECKING OF COMPUTATIONS, Discovering and certifying lower bounds for the online bin stretching problem, Hardness of learning problems over Burnside groups of exponent 3, Cogent: uniqueness types and certifying compilation, Self-testing/correcting with applications to numerical problems, A framework for the verification of certifying computations, Tight bounds on expected time to add correctly and add mostly correctly, \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
