Designing programs that check their work
From MaRDI portal
Publication:4369864
DOI10.1145/200836.200880zbMATH Open0886.68046OpenAlexW1996839061MaRDI QIDQ4369864FDOQ4369864
Authors: Sampath Kannan, Manuel Blum 
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
Recommendations
Cited In (80)
- A nonadaptive NC checker for permutation group intersection
- On the power of multi-prover interactive protocols
- A framework for developing stand-alone certifiers
- Pipelined algorithms to detect cheating in long-term grid computations
- Title not available (Why is that?)
- Approximate testing with error relative to input size.
- A self-certifying compilation framework for WebAssembly
- Quasi-random words and limits of word sequences
- Efficient authenticated data structures for graph connectivity and geometric search problems
- Certification of computational results
- Test suite oscillations
- Checking the correctness of memories
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Lower bounds for 2-query LCCs over large alphabet
- A low complexity probabilistic test for integer multiplication
- Secure outsourcing of modular exponentiations under single untrusted programme model
- Recent progress in exact geometric computation
- The power of adaptiveness and additional queries in random-self- reductions
- Speeding up exponentiation using an untrusted computational resource
- Fast approximate probabilistically checkable proofs
- A framework for the verification of certifying computations
- Automatic result verification by complete run-time checking of computations
- Checker for data structures which sort elements
- Lower bounds on assumptions behind indistinguishability obfuscation
- Farkas certificates and minimal witnesses for probabilistic reachability constraints
- Foundations of homomorphic secret sharing
- On the Complexity of the Hidden Subgroup Problem
- Self-testing/correcting with applications to numerical problems
- Efficient and secure delegation of exponentiation in general groups to a single malicious server
- Program verification: to err is human
- Problem identification using program checking
- Spot-checkers
- A self-tester for linear functions over the integers with an elementary proof of correctness
- On matrix rigidity and locally self-correctable codes
- Title not available (Why is that?)
- Locality and checkability in wait-free computing
- Locality and checkability in wait-free computing
- Low redundancy polynomial checks for numerical computation
- A survey on delegated computation
- Property testing of regular tree languages
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Deterministically testing sparse polynomial identities of unbounded degree
- Efficient checkers for number-theoretic computations
- Linear-size constant-query IOPs for delegating computation
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- An efficient local approach to convexity testing of piecewise-linear hypersurfaces
- Title not available (Why is that?)
- Certifying algorithms
- Discovering and certifying lower bounds for the online bin stretching problem
- Checking the convexity of polytopes and the planarity of subdivisions
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Tight bounds on expected time to add correctly and add mostly correctly
- Batch checking with applications to linear functions
- Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces
- Program result checking: a new approach to making programs more reliable
- Title not available (Why is that?)
- Algebraic testing and weight distributions of codes.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Testing nonlinear operators
- On locally decodable codes, self-correctable codes, and \(t\)-private PIR
- On the complexity of the hidden subgroup problem
- Cogent: uniqueness types and certifying compilation
- High-entropy dual functions over finite fields and locally decodable codes
- Hardness of learning problems over Burnside groups of exponent 3
- Outlaw distributions and locally decodable codes
- Self-correcting for function fields of finite transcendental degree
- Linear-consistency testing.
- Title not available (Why is that?)
- Testing membership for timed automata
- Checking the convexity of polytopes and the planarity of subdivisions (extended abstract)
- A note on the self-witnessing property of computational problems
- The journey from NP to TFNP hardness
- A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING
- Capturing one-way functions via NP-hardness of meta-complexity
- Checking properties of polynomials
- \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem
- An information-theoretic treatment of random-self-reducibility (extended abstract)
- Construction sequences and certifying 3-connectivity
- Nearly exact mining of frequent trees in large networks
This page was built for publication: Designing programs that check their work
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4369864)
