Introduction to Property Testing

DOI10.1017/9781108135252OpenAlexW2769478807MaRDI QIDQ5371343

Oded Goldreich

Publication date: 25 October 2017

Full work available at URL: https://semanticscholar.org/paper/28816b148281af9ba41469b4c69dd69c2afd2b95

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Randomized algorithms (68W20)

Related Items (79)

Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs ⋮ Testing graphs against an unknown distribution ⋮ Hypothesis testing for high-dimensional multinomials: a selective review ⋮ Algorithms that access the input via queries ⋮ An adaptivity hierarchy theorem for property testing ⋮ A characterization of easily testable induced digraphs and \(k\)-colored graphs ⋮ Polynomial removal lemmas for ordered graphs ⋮ A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ Concentration of the collision estimator ⋮ Collision-based Testers are Optimal for Uniformity and Closeness ⋮ An optimal tester for \(k\)-linear ⋮ Estimating the number of connected components in a graph via subgraph sampling ⋮ Property testing and expansion in cubical complexes ⋮ Statistical difference beyond the polarizing regime ⋮ Unnamed Item ⋮ On the Effect of the Proximity Parameter on Property Testers ⋮ On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing ⋮ On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition) ⋮ The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution ⋮ A Note on Tolerant Testing with One-Sided Error ⋮ Reducing Testing Affine Spaces to Testing Linearity of Functions ⋮ On the Optimal Analysis of the Collision Probability Tester (an Exposition) ⋮ Flexible Models for Testing Graph Properties ⋮ Testing linear inequalities of subgraph statistics ⋮ On one-sided testing affine subspaces ⋮ Stability of approximate group actions: uniform and probabilistic ⋮ A lower bound on the complexity of testing grained distributions ⋮ Erasures versus errors in local decoding and property testing ⋮ Testability in group theory ⋮ Locally verifiable signature and key aggregation ⋮ Almost optimal proper learning and testing polynomials ⋮ Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu ⋮ Almost optimal query algorithm for hitting set using a subset query ⋮ A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification ⋮ Global information from local observations of the noisy voter model on a graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Bradley-Terry condition is \(L_1\)-testable ⋮ Unnamed Item ⋮ Local-vs-global combinatorics ⋮ An optimal tester for \(k\)-Linear ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Efficient Testing without Efficient Regularity ⋮ Zero-Knowledge Proofs of Proximity ⋮ Proofs of Proximity for Distribution Testing ⋮ An Exponential Separation Between MA and AM Proofs of Proximity ⋮ The power and limitations of uniform samples in testing properties of figures ⋮ On the tree-width of even-hole-free graphs ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Unnamed Item ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems ⋮ Almost Optimal Testers for Concise Representations. ⋮ Property testing lower bounds via a generalization of randomized parity decision trees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Testing piecewise functions ⋮ Smooth and strong PCPs ⋮ Hierarchy theorems for testing properties in size-oblivious query complexity ⋮ No-signaling linear PCPs ⋮ Quasi-random words and limits of word sequences ⋮ Testing for Dense Subsets in a Graph via the Partition Function ⋮ Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs ⋮ Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs ⋮ \(k\)-hop graph neural networks ⋮ A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling ⋮ Every Set in P Is Strongly Testable Under a Suitable Encoding ⋮ Improved bounds for quantified derandomization of constant-depth circuits and polynomials ⋮ Two Party Distribution Testing: Communication and Security ⋮ Quantum Chebyshev's Inequality and Applications ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ Unnamed Item ⋮ On the Query Complexity of Estimating the Distance to Hereditary Graph Properties ⋮ An explicit construction of graphs of bounded degree that are far from being Hamiltonian ⋮ Topics and Techniques in Distribution Testing: A Biased but Representative Sample ⋮ A PCP of proximity for real algebraic polynomials

This page was built for publication: Introduction to Property Testing