On Proximity-Oblivious Testing

DOI10.1137/100789646MaRDI QIDQ3020015zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Dana Ron

Publication date 29 July 2011

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/100789646

zbMATH Keywords

detection probabilitygraph propertiesproperty testingproximity oblivious testsproximity parameter

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• On proximity oblivious testing
• Proximity oblivious testing and the role of invariances
• Proximity Oblivious Testing and the Role of Invariances
• Two-sided error proximity oblivious testing
• Two-sided error proximity oblivious testing (extended abstract)
• Universally composable private proximity testing
• Proofs of proximity for distribution testing
• GSF-locality is not sufficient for proximity-oblivious testing
• Towards a notion of testability

Cited in

(33)

• Proofs of proximity for context-free languages and read-once branching programs
• Non-interactive proofs of proximity
• A non-extendibility certificate for submodularity and applications
• On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
• Tolerant property testing and distance approximation
• Two-sided error proximity oblivious testing
• Partial tests, universal tests and decomposability
• Tolerant versus intolerant testing for Boolean properties
• Two-sided error proximity oblivious testing (extended abstract)
• Proofs of proximity for context-free languages and read-once branching programs
• Erasure-Resilient Property Testing
• Parameterized property testing of functions
• On sample-based testers
• Efficient testing without efficient regularity
• Explicit strong LTCs with inverse poly-log rate and constant soundness
• Testing local properties of arrays
• Every Set in P Is Strongly Testable Under a Suitable Encoding
• The subgraph testing model
• Testing Linear-Invariant Properties
• On the Effect of the Proximity Parameter on Property Testers
• Optimal unateness testers for real-valued functions: adaptivity helps
• On proximity oblivious testing
• An explicit construction of graphs of bounded degree that are far from being Hamiltonian
• Proximity Oblivious Testing and the Role of Invariances
• Proximity oblivious testing and the role of invariances
• Testing linear inequalities of subgraph statistics
• scientific article; zbMATH DE number 7758318 (Why is no real title available?)
• GSF-locality is not sufficient for proximity-oblivious testing
• On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
• On the query complexity of testing local graph properties in the bounded-degree graph model
• Testing isomorphism in the bounded-degree graph model
• On locally-characterized expander graphs (a survey)
• Testing depth first search numbering

This page was built for publication: On Proximity-Oblivious Testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3020015)