Spot-checkers
From MaRDI portal
Publication:1577018
DOI10.1006/jcss.1999.1692zbMath0961.68036OpenAlexW3023302315WikidataQ105583261 ScholiaQ105583261MaRDI QIDQ1577018
Mahesh Viswanathan, S. Ravi Kumar, Ronitt Rubinfeld
Publication date: 28 May 2001
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1999.1692
Related Items (41)
Testing Lipschitz functions on hypergrid domains ⋮ Fast approximate probabilistically checkable proofs ⋮ On the strength of comparisons in property testing ⋮ Parameterized property testing of functions ⋮ On the benefits of adaptivity in property testing of dense graphs ⋮ Property testing for cyclic groups and beyond ⋮ Locally Decodable Codes for Edit Distance ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Improved algorithm for permutation testing ⋮ Quantum property testing of group solvability ⋮ Unnamed Item ⋮ Erasure-Resilient Property Testing ⋮ Locality and checkability in wait-free computing ⋮ Monotonicity testing and shortest-path routing on the cube ⋮ Distribution-free connectivity testing for sparse graphs ⋮ Testing Euclidean Spanners ⋮ Hierarchy Theorems for Property Testing ⋮ The power and limitations of uniform samples in testing properties of figures ⋮ Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces ⋮ Adaptive Lower Bound for Testing Monotonicity on the Line ⋮ Property testing lower bounds via communication complexity ⋮ Estimating the Longest Increasing Sequence in Polylogarithmic Time ⋮ Problem identification using program checking ⋮ Fast approximate PCPs for multidimensional bin-packing problems ⋮ Testing permutation properties through subpermutations ⋮ Testing hypergraph colorability ⋮ Transitive-Closure Spanners: A Survey ⋮ Invariance in Property Testing ⋮ Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity ⋮ Local Property Reconstruction and Monotonicity ⋮ Unnamed Item ⋮ Testing piecewise functions ⋮ Tolerant property testing and distance approximation ⋮ Earthmover Resilience and Testing in Ordered Structures ⋮ An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube ⋮ Hardness of learning loops, monoids, and semirings ⋮ On the Complexity of Computational Problems Regarding Distributions ⋮ Locality and Checkability in Wait-Free Computing ⋮ Unnamed Item ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non-deterministic exponential time has two-prover interactive protocols
- Self-testing/correcting with applications to numerical problems
- Efficient checkers for number-theoretic computations
- Fast approximate PCPs
- Proof verification and the hardness of approximation problems
- Property testing and its connection to learning and approximation
- Probabilistic checking of proofs
- Designing programs that check their work
- Interactive proofs and the hardness of approximating cliques
- Reflections on the Pentium division bug
- Robust Characterizations of Polynomials with Applications to Program Testing
- Checking approximate computations over the reals
This page was built for publication: Spot-checkers
